Description

Given a sequence of length $n$, you may subtract a number from some elements so that the whole sequence becomes strictly increasing.

You need to find the minimum possible value of the sum of all numbers subtracted.

For example, for a sequence of length $3$: $5,5,5$. The best plan is $5-2,5-1,5$, i.e. $3,4,5$. Then the sum of all subtracted numbers is $2+1=3$, which is the minimum.

Input Format

The first line contains an integer $n$, representing the length of the sequence.

The second line contains $n$ integers describing the sequence.

Output Format

Output one integer in one line, representing the minimum total sum.

3
5
5
5

3

4
5
3
7
5

6

Hint

Constraints and Notes

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 100$, and all numbers in the sequence are positive integers not greater than $20000$.

Notes

Translated from COCI2010-2011 CONTEST #6 T3 RAZINE。

Translated by ChatGPT 5