Minimum Operations to Make Sequence Strictly Increasing

You are given a sequence of n non-negative integers. In one operation, you can increment any element of the sequence by 1. The goal is to transform the sequence into a strictly increasing sequence with the minimum number of operations.

A sequence a₁, a₂, ..., a_n is strictly increasing if a₁ < a₂ < ... < a_n.

Formally, you need to find the minimum total number of increments needed so that for every i (2 ≤ i ≤ n), the condition a_i > a_i-1 holds.

The relation between increments and the condition can be mathematically expressed as follows. For each index i (2 ≤ i ≤ n), if the current value a_i is not strictly greater than a_i-1, you need to perform:

[ \text{increments} = a_{i-1} - a_i + 1 ]

Update the value of a_i to a_i-1 + 1 after performing the increments. Your task is to compute the sum of all such required increments.

inputFormat

The first line of input contains an integer n (1 ≤ n ≤ 10⁵), representing the number of elements in the sequence.

The second line contains n space-separated non-negative integers representing the sequence.

outputFormat

Output a single integer, the minimum number of operations required to make the sequence strictly increasing.

## sample

4
1 2 2 4

1

</p>