← 返回题目列表

AtCoder · awc0043_d

D. 高度差之和

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

分数: 400 分

问题陈述

在高桥的班级里,学生们按照身高顺序排队上体育课。老师想了解学生身高的分布情况,因此他们决定计算所有成对学生的身高差之和。

有 N 班里的学生,以及身高 i第学生是 A_i 厘米。

老师想要找到每个组合的高度绝对差异 2 从以下学校中选出的不同学生 N 同学,并计算总和。

具体来说,对于所有对 (i, j) 满意 1 \leq i < j \leq N,计算 |A_i - A_j| 并找出它们的总和。即使两个学生身高相同,只要是不同的个体,就算作一对。

约束

  • 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
  • 第一行包含一个整数 N,代表学生人数。
  • 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表学生的身高。
  • A_i 表示高度(以厘米为单位) i第一个学生。

输出

在一行中打印 |A_i - A_j| 所有对 (i, j) 满意 1 \leq i < j \leq N.


示例输入 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