分数: 400 点
问题陈述
给出的是 N 整数 A_1,\ldots,A_N.
求总和 |A_i-A_j| 所有对 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
输出
打印答案。
示例输入 1
3 5 1 2
示例输出 1
8
我们有 |5-1|+|5-2|+|1-2|=8.
示例输入 2
5 31 41 59 26 53
示例输出 2
176