Differences

Interview

Time limit1sMemory limit1024 MB

Summary

Given N scores, the task is to sum the absolute differences over all pairs of scores efficiently.

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

문제

Students from the science-track classes of Juku's school took part in an informatics olympiad. Now the teacher analyzes the results and wants to know which class has the most even level of students and which has the least even.

The difference between two students' results is the higher score minus the lower score. To measure how uneven a class is, the teacher takes every pair of students, adds up the differences for all pairs, and divides the sum by the number of pairs. Dividing by the number of pairs is one simple operation. Adding up all the differences is tedious, so Juku plans to write a program for it as his capstone project.

Juku's ambitions go further. He wants to start a student company that analyzes results for cities as well as for schools. Big cities have hundreds of thousands of students, so the program must be efficient enough for large data sets. Help Juku write this program!

입력

The first line contains the number of students $N$ ( $2 \le N \le 100\,000$ ). The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ separated by spaces ( $0 \le A_i \le 1\,000$ ), the students' results.

출력

Print one line with the sum of the differences between the results given in the input.

Examples1

Example 1
Input
```
3
1 4 2
```
Expected output
```
6
```