Problem Description

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.

Input Format

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 Format

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

5
1 2 3 4 5

20

10
0 0 0 0 0 10000000 0 0 0 0

90000000

Hint

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.

Translated by ChatGPT 5