D - Sum of Height Differences Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君のクラスでは、体育の授業で背の順に並ぶことになりました。先生は生徒同士の身長がどれくらい散らばっているかを把握するため、すべての生徒のペアについて身長差の総和を調べることにしました。

クラスには N 人の生徒がおり、i 番目の生徒の身長は A_i センチメートルです。

先生は、N 人の中から異なる 2 人を選ぶすべての組み合わせについて、身長の差の絶対値を求め、その総和を計算したいと考えています。

すなわち、1 \leq i < j \leq N を満たすすべてのペア (i, j) について |A_i - A_j| を計算し、その総和を求めてください。身長が同じ生徒がいる場合でも、異なる人物の組であればそれぞれ 1 つのペアとして数えます。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^8
  • 入力はすべて整数
  • 答えは 2^{63} - 1 以下であることが保証される（64ビット符号付き整数型に収まる）

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、生徒の人数を表す整数 N が与えられる。
  • 2 行目には、各生徒の身長を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
  • A_i は i 番目の生徒の身長（センチメートル）を表す。

出力

1 \leq i < j \leq N を満たすすべてのペア (i, j) についての |A_i - A_j| の総和を 1 行で出力せよ。

入力例 1

4
150 160 170 180

出力例 1

100

入力例 2

5
160 160 150 170 150

出力例 2

100

入力例 3

10
172 165 180 158 165 190 175 168 182 160

出力例 3

551

入力例 4

20
145 172 168 190 155 160 177 182 149 171 166 158 193 174 169 161 185 152 178 164

出力例 4

2975

入力例 5

2
1 100000000

出力例 5

99999999

Score : 400 pts

Problem Statement

In Takahashi's class, students are to line up in order of height for their physical education class. The teacher wants to understand how spread out the students' heights are, so they decided to calculate the sum of height differences for all pairs of students.

There are N students in the class, and the height of the i-th student is A_i centimeters.

The teacher wants to find the absolute difference in height for every combination of 2 distinct students chosen from the N students, and calculate the total sum.

Specifically, for all pairs (i, j) satisfying 1 \leq i < j \leq N, compute |A_i - A_j| and find their total sum. Even if two students have the same height, as long as they are different individuals, they are counted as one pair.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^8
  • All inputs are integers.
  • It is guaranteed that the answer is at most 2^{63} - 1 (fits in a 64-bit signed integer).

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N, representing the number of students.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the heights of the students.
  • A_i represents the height (in centimeters) of the i-th student.

Output

Print in one line the sum of |A_i - A_j| over all pairs (i, j) satisfying 1 \leq i < j \leq N.

Sample Input 1

4
150 160 170 180

Sample Output 1

100

Sample Input 2

5
160 160 150 170 150

Sample Output 2

100

Sample Input 3

10
172 165 180 158 165 190 175 168 182 160

Sample Output 3

551

Sample Input 4

20
145 172 168 190 155 160 177 182 149 171 166 158 193 174 169 161 185 152 178 164

Sample Output 4

2975

Sample Input 5

2
1 100000000

Sample Output 5

99999999