Sum of Absolute Differences

You are given a list of n integers. Your task is to calculate the sum of absolute differences of all possible unordered pairs. In other words, you should compute:

\( \displaystyle S = \sum_{1 \le i < j \le n} |a_i - a_j| \)

This problem requires you to carefully analyze and optimize the calculation when n is large. For instance, for the input list [1, 3, 5], the pairs are (1,3), (1,5) and (3,5) with absolute differences 2, 4, and 2, respectively, summing to 8.

inputFormat

The first line of input contains an integer n (1 ≤ n ≤ 10⁵), the number of integers.

The second line contains n integers separated by spaces. Each integer can be positive, negative, or zero.

outputFormat

Output a single integer which is the sum of the absolute differences of all pairs.

3
1 3 5

8