题目描述

来自信息学小组“卡皮巴拉编程”的学生们参加了一场比赛。根据比赛结果，第 $i$ 名学生获得了 $a_i$ 分。

为了鼓励参与者，小组负责人亚历山大·伊戈列维奇决定给学生们发糖果。对于所有 $i$ 和 $j$，如果第 $i$ 名学生得分比第 $j$ 名学生高，那么负责人会给第 $i$ 名学生 $a_i - a_j$ 颗糖果。

帮助负责人计算，他需要准备多少糖果来分发给学生们。

输入格式

输入数据的第一行给定一个数字 $n$ —— 学生数量（$1 \le n \le 500\,000$）。

第二行包含 $n$ 个整数 $a_i$ —— 小组成员在比赛中的成绩（$0 \le a_i \le 10^7$）。

输出格式

输出一个数字 —— 需要准备分发给学生的糖果总数。

5
1 2 3 4 5

20

10
0 0 0 0 0 10000000 0 0 0 0

90000000

提示

注意

请注意，此问题的答案可能超过 32 位整数变量的可能值，因此必须使用 64 位整数数据类型（Pascal 语言中的 int64 类型，C++ 中的 long long 类型，Java 和 C# 中的 long 类型）。

样例解释

在第一个样例中，第一名学生不会得到糖果，第二名学生将得到 1 颗糖果，第三名学生将得到 $1+2=3$ 颗糖果，第四名学生将得到 $1+2+3=6$ 颗糖果，第五名学生将得到 $1+2+3+4=10$ 颗糖果。

评分规则

每个子任务的分数仅在该子任务及其所有必需子任务的全部测试通过时授予。

子任务	分值	额外限制	必需子任务
1	15	$1 \le n \le 1\,000$
2	5	所有 $a_i$ 相同
3		对于任意 $i \ne j$，有 $a_i \ne a_j$，且 $1 \le a_i \le n$
4	10	$0 \le a_i \le 1$
5	15	$0 \le a_i \le 100$	4
6		$a_i$ 中最多有两个不同的值	2, 4
7	35	无	1–6

翻译由 DeepSeek 完成