Sum of Distances 2

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given n coordinates on a line, compute the sum of absolute differences over all ordered pairs.

Level: Medium4 of 10
Topics: Sorting, Prefix sum, Math, Array
Solved: No attempts yet

Problem

There are n points on a number line. Given the x-coordinate of each point, write a program that computes the sum of |x[i] - x[j]| over all pairs (i, j).

Input

The first line contains n (1 ≤ n ≤ 500,000). The second line contains x[1], x[2], x[3], …, x[n]. Each is an integer between 0 and 10,000,000 inclusive.

Output

Print the answer on the first line.

Examples1

Example 1
Input
```
5
1 5 3 2 4
```
Expected output
```
40
```