Minimum Total Subtraction for a Strictly Increasing Sequence

You are given a sequence of n integers \(A = [A_0, A_1, \ldots, A_{n-1}]\). You are allowed to subtract a non-negative integer from each of the numbers (each subtraction can be different for different indices) so that the resulting sequence \(B = [B_0, B_1, \ldots, B_{n-1}]\) is strictly increasing (i.e. \(B_0 < B_1 < \cdots < B_{n-1}\)).

Your task is to find the minimum possible total subtraction, i.e. \(\sum_{i=0}^{n-1} (A_i - B_i)\), that can be achieved.

Note: You are not allowed to add to any element; you may only subtract a non-negative integer from each element.

Example: Consider \(n=3\) and \(A = [5, 5, 5]\). One optimal solution is to subtract 2 from the first element and 1 from the second element to form \(B = [3, 4, 5]\). The total subtraction is \(2+1=3\), which is the minimum total subtraction.

inputFormat

The first line contains a single integer \(n\) indicating the length of the sequence.

The second line contains \(n\) space-separated integers \(A_0, A_1, \ldots, A_{n-1}\) representing the sequence.

outputFormat

Output a single integer representing the minimum possible total subtraction needed to make the sequence strictly increasing.

sample

3
5 5 5

3