Dongjun's Game

Interview

Time limit1sMemory limit128 MB

Summary

Given N level scores, find the minimum total decrease needed to make the sequence strictly increasing while all scores stay positive.

Level: Medium5 of 10
Topics: Greedy, Array, Dynamic programming
Solved: No attempts yet

Problem

Dongjun made a smartphone game based on what he learned in graphics class. The game has N levels arranged in increasing order of difficulty. Clearing each level gives a fixed score. A player's total score is the sum of the scores from cleared levels, and the online ranking is based on that total.

Scores should become larger as the levels become harder. However, some easier levels were assigned scores that are greater than or equal to the scores of later, harder levels.

Dongjun wants to decrease the scores of some levels by 1 point at a time so that the scores strictly increase from the first level to the last level. Every score must remain positive. Decreasing a score by 1 counts as one decrease. Among all valid adjustments, find the minimum total number of decreases needed. The input is always such that a valid answer exists.

Input

The first line contains the number of levels N. (1 <= N <= 100)

Each of the next N lines contains the score obtained by clearing one level, from the first level to the last level. Each score is a positive integer less than 20,000.

Output

Print the minimum number of decreases needed to make the final scores strictly increasing.

Examples2

Example 1
Input
```
3
5
5
5
```
Expected output
```
3
```
Example 2
Input
```
4
5
3
7
5
```
Expected output
```
6
```