P101863 - [AtCoder]ABC186 D - Sum of difference - SSOJ

Memory Limit：256 MB Time Limit：2 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

Score : $400$ points

Problem Statement

Given are $N$ integers $A_1,\ldots,A_N$.

Find the sum of $|A_i-A_j|$ over all pairs $i,j$ such that $1\leq i < j \leq N$.

In other words, find $\displaystyle{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i-A_j|}$.

Constraints

$2 \leq N \leq 2 \times 10^5$
$|A_i|\leq 10^8$
$A_i$ is an integer.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

3
5 1 2

Sample Output 1

We have $|5-1|+|5-2|+|1-2|=8$.

Sample Input 2

5
31 41 59 26 53

Sample Output 2

题意翻译

### 题意简述高桥君~~又~~想了一个新游戏。输入 $n$ 个整数 $a_1,a_2,...a_n$，求在满足 $1 \leq i < j \leq n$ 的所有 $\lvert a_i-a_j \rvert$ 的和 $X$ 。即求$X=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \lvert a_i-a_j\rvert$ 。 ### 输入格式第一行是一个整数 $n$ , 第二行是 $n$ 个整数 $a_1,a_2...a_n$。所有数据保证 $2 \leq n \leq 10^5,\lvert a_i\rvert \leq 10^8。$ ### 输出格式输出所求的 $X$ 。

普及一等 ABC186 D Atcoder

101863: [AtCoder]ABC186 D - Sum of difference

Description

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Input

题意翻译

Source/Category

加入题单