← 返回题目列表

AtCoder · abc186_d

D. 差值总和

中文机器翻译题面 查看原题

分数: 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