Minimum increments

Input

The first line contains a single integer $n (n \leq 1 0^{6})$ n~(n \le 10^6).

The second line contains $n$ positive integers, each not exceeding $1 0^{6}$ 10^6.

Print the minimum number of operations required to transform the array into an arithmetic progression with a difference of $1$ .

In the first test, the array should be transformed into:

89101112

8~9~10~11~12

To do this, we need

(8 - 3) + (9 - 6) + (10 - 4) + (11 - 11) + (12 - 5) = 5 + 3 + 6 + 0 + 7 = 21

(8 - 3) + (9 - 6) + (10 - 4) + (11 - 11) + (12 - 5) = 5 + 3 + 6 + 0 + 7 = 21

operations.

Example 1

Loading

Example 2

Loading