COCI '10 Contest 6 #3 Razine

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

Mirko has developed his own video game. The game has N levels and each successfully completed level is worth a certain number of points, which add up to the player's total score on an online rank list of all players. Mirko has ordered his levels by difficulty from the easiest to the most difficult, but he has made a mistake and made some difficult levels worth less points than some of the easier ones.

To overcome this problem, Mirko has decided to reduce the number of points for certain levels with the goal of making the point sequence strictly increasing (so in the end easier levels are worth less points than the difficult ones).

Help Mirko fix his video game in such a way that the total number of points reduced is minimal. Final points have to be positive. You can assume that a solution exists for each test case.

Input Specification

The first line of input contains one positive integer N (1 \le N \le 100), the number of levels.

The next N lines contain positive integers less than 20\,000, the number of points that Mirko has associated with each level, from the first to the last level.

Output Specification

The first and only line of output should contain one number - the minimum total number of points Mirko has to subtract to fulfill requirements given in the task statement above.

Sample Input 1

3
5
5
5

Sample Output 1

3

Sample Input 2

4
5
3
7
5

Sample Output 2

6

Comments

There are no comments at the moment.