LCC/Moose '20 Contest 2 J3 - Alan's Snowmen

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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

Comments

There are no comments at the moment.