信息学兴趣小组“水豚在写代码”的学生们参加了奥林匹克竞赛。根据竞赛结果，第 $i$ 个学生获得了 $a_i$ 分。
为了奖励参赛者，兴趣小组的负责人亚历山大·谢尔盖耶维奇决定给学生们分发糖果。对于任意 $i$ 和 $j$，如果第 $i$ 个学生的得分严格大于第 $j$ 个学生的得分，那么负责人就会给第 $i$ 个学生 $a_i - a_j$ 颗糖果。
请你帮助负责人计算，他总共需要准备多少颗糖果来分发给学生们。
输入格式
第一行输入一个整数 $n$ —— 学生人数（$1 \le n \le 5\,000\,000$）。
第二行包含 $n$ 个整数 $a_i$ —— 兴趣小组成员在奥林匹克竞赛中的成绩（$0 \le a_i \le 10^7$）。
输出格式
输出一个整数 —— 需要准备的糖果总数。
请注意，本题的答案可能超过 32 位整数的表示范围，因此需要使用 64 位整数类型（Pascal 中的 int64，C++ 中的 long long，Java 和 C# 中的 long）。
子任务
每个子任务的分数只有在该子任务以及其所依赖的所有子任务的测试全部通过时才会计入。
| 子任务 | 分值 | 附加限制 | 必要子任务 |
|---|---|---|---|
| 1 | 15 | $1 \le n \le 1000$ | — |
| 2 | 5 | 所有 $a_i$ 相同 | — |
| 3 | 5 | 对任意 $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 | 15 | $a_i$ 中至多存在两种不同的值 | 2, 4 |
| 7 | 35 | — | 1–6 |
样例数据
标准输入
5 1 2 3 4 5
标准输出
20
标准输入
10 0 0 0 0 0 10000000 0 0 0 0
标准输出
90000000
说明
在第一个样例中，第一个学生不会获得糖果；第二个学生获得 $1$ 颗糖果；第三个学生获得 $1+2=3$ 颗糖果；第四个学生获得 $1+2+3=6$ 颗糖果；第五个学生获得 $1+2+3+4=10$ 颗糖果。