[AdditionalFile5564.zip](file://AdditionalFile5564.zip?type=additional_file)

#5564. 「ROIR 2026 Day1」比赛结果

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI Regional 2026 Day1 T1. Итоги олимпиады

「卡皮巴拉编码」信息学俱乐部的学生们参加了一场编程奥运会。第 $i$ 个学生在比赛中获得了 $a_i$ 分。

为了鼓励大家，俱乐部负责人亚历山大·伊戈列维奇决定发放糖果。具体的发放规则如下：

• 对于任意两个学生 $i$ 和 $j$，如果 $a_i > a_j$，则给第 $i$ 个学生发放 $a_i - a_j$ 颗糖果。

请帮助负责人计算，他总共需要准备多少颗糖果。

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 500000)$，表示参加比赛的学生人数。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(0 \leq a_i \leq 10^7)$，表示每个学生的得分。

输出格式

输出一个整数，表示总共需要准备的糖果数量。

注意：答案可能非常大（超过 32 位整数范围），请务必使用 64 位整数类型（如 C++ 的 long long、Pascal 的 int64、Java/C# 的 long）。

样例 1

输入

5
1 2 3 4 5

输出

20

第一个学生不得糖果；第二个学生得 $1$ 颗；第三个学生得 $1+2=3$ 颗；第四个学生得 $1+2+3=6$ 颗；第五个学生得 $1+2+3+4=10$ 颗。

样例 2

输入

10
0 0 0 0 0 10000000 0 0 0 0

输出

90000000

数据范围与提示

详细子任务附加限制及分值如下表所示。