P15127 [ROIR 2026] Contest Results

Students from the informatics group "Kapibara Programming" took part in a contest. According to the results, the student in position $i$ scored $a_i$ points. To encourage the participants, the group leader Alexander Igorevich decided to give the students candies. For all $i$ and $j$, if the student in position $i$ has a higher score than the student in position $j$, then the leader will give the student in position $i$ $a_i - a_j$ candies. Help the leader compute how many candies he needs to prepare to distribute to the students.

The first line of the input gives an integer $n$ — the number of students ($1 \le n \le 500\,000$). The second line contains $n$ integers $a_i$ — the contest scores of the group members ($0 \le a_i \le 10^7$).

Output one number — the total number of candies that need to be prepared for distribution to the students.

### Note Please note that the answer to this problem may exceed the possible value of a 32-bit integer variable, so you must use a 64-bit integer data type (`int64` in Pascal, `long long` in C++, `long` in Java and C#). ### Sample Explanation In the first sample, the first student will not receive any candies, the second student will receive 1 candy, the third student will receive $1+2=3$ candies, the fourth student will receive $1+2+3=6$ candies, and the fifth student will receive $1+2+3+4=10$ candies. ### Scoring Rules The score for each subtask is awarded only if all testdata in that subtask and all its required subtasks are passed. | **Subtask** | **Points** | **Additional Constraints** | **Required Subtasks** | |:----------:|:--------:|:---------------------------:|:---------------------:| | 1 | 15 | $1 \le n \le 1\,000$ | | | 2 | 5 | All $a_i$ are the same | | | 3 | 5 | For any $i \ne j$, $a_i \ne a_j$, and $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 | There are at most two distinct values among $a_i$ | 2, 4 | | 7 | 35 | None | 1–6 | Translated by ChatGPT 5