Alan has a line of ~N~ snowmen! Each snowman is made of ~a_i~ snowballs. Alan wants every snowman to be at least as tall (having at least as many snowballs) as all the snowmen earlier than it, so he will need to add snowballs to some of the snowmen. Can you help Alan find the minimum number of snowballs he needs to add?

Input Specification

The first line will contain ~N\ (1 \le N \le 10^5)~. The next line will contain ~N~ integers ~a_i\ (1 \le a_i \le 10^9)~.

Output Specification

Output the minimum number of snowballs Alan needs to add. Note that 64-bit integers may be required to pass.

Subtasks

Subtask 1 [30%]

~N \le 10^3~

Subtask 2 [70%]

No further constraints.

Sample Input

6
2 8 4 9 8 7

Sample Output

7