You are given an array of n integers. You want to modify the array so that it is strictly increasing, i.e., every element is larger than previous element.

On each move, you can increase the value of any element by one. What is the minimum number of moves required?

Constraints

1 ≤ n ≤ 2*10⁵

1 ≤ a[i] ≤ 10⁹

Input

 First line contains one integer n - size of the array.

 Second line contains n space separated integers a₁,a₂,…,a_n.

Output

Print the number of moves required to make the array strictly increasing.