Students from the informatics club “Capybaras Code” are participating in an olympiad. According to the results of the olympiad, the $i$-th student scored $a_i$ points.
To encourage the participants, the club leader Aleksandr Sergeevich decided to give candies to the students. For all $i$ and $j$, if the $i$-th student scored more points than the $j$-th student, then the leader gives the $i$-th student $a_i - a_j$ candies.
Help the leader determine the total number of candies he needs to prepare to distribute to the students.
Input Format
The first line contains an integer $n$ — the number of students ($1 \le n \le 500,000$).
The second line contains $n$ integers $a_i$ — the results of the club participants in the olympiad ($0 \le a_i \le 10^7$).
Output Format
Output a single number — the total number of candies that need to be prepared to distribute to the students.
Note that the answer in this problem may exceed the range of a 32-bit integer type, so you must use 64-bit integer types (type int64 in Pascal, type long long in C++, type long in Java and C#).
Scoring
Points for each subtask are awarded only if all tests for that subtask and all required subtasks are successfully passed.
Subtasks
| Subtask | Points | Additional Constraints | Required Subtasks |
|---|---|---|---|
| 1 | 15 | $1 \le n \le 1,000$ | — |
| 2 | 5 | All $a_i$ are equal | — |
| 3 | 5 | For any $i \ne j$, $a_i \ne a_j$, also $1 \le a_i \le n$ | — |
| 4 | 10 | $0 \le a_i \le 1$ | — |
| 5 | 15 | $0 \le a_i \le 10^4$ | — |
| 6 | 15 | There are at most two distinct values among $a_i$ | 2, 4 |
| 7 | 35 | — | 1–6 |
Example
Input
5 1 2 3 4 5
Output
20
Input
10 0 0 0 0 0 10000000 0 0 0 0
Output
90000000
Note
In the first example, the first student receives no candies, the second student receives 1 candy, the third student receives $1 + 2 = 3$ candies, the fourth student receives $1 + 2 + 3 = 6$ candies, and the fifth student receives $1 + 2 + 3 + 4 = 10$ candies.