D - 两数差的和

得分：400 分

题目描述

给定 $N$ 个整数 $A_1,\ldots,A_N$。

求所有不同的数对 $i,j$（$1\leq i < j \leq N$）的差的绝对值之和。

换句话说，找到 $\displaystyle{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i-A_j|}$。

限制

• $2 \leq N \leq 2 \times 10^5$
• $|A_i|\leq 10^8$
• $A_i$ 是整数。

输入

输入在以下格式从标准输入中给出：

$N$

$A_1$ $\ldots$ $A_N$

输出

输出答案。

3
5 1 2

8

我们有 $|5-1|+|5-2|+|1-2|=8$。

5
31 41 59 26 53

176

我们有 $|31-41|+|31-59|+|31-26|+|31-53|+|41-59|+|41-26|+|41-53|+|59-26|+|59-53|+|26-53|=176$。