Problem 54: Minimum Operations to Make Array Strictly Increasing

Problem Statement: Given an array of integers, determine the minimum number of increments (increasing any element by 1 per operation) required to make the array strictly increasing.

Input

The first line contains an integer n. The next line contains n space-separated integers.

Output

Print the minimum number of operations needed.

Examples


Input:
5
1 1 1 1 1

Output:
10

Solution Explanation

Iterate over the array, and whenever an element is not greater than the previous one, increment it to previous+1, and accumulate the difference. This greedy method ensures minimal operations.

Solution in C++


#include 
#include 
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    cin >> n;
    vector a(n);
    for(int i = 0; i < n; i++) 
        cin >> a[i];
    long long operations = 0;
    for(int i = 1; i < n; i++){
        if(a[i] <= a[i-1]){
            int diff = a[i-1] + 1 - a[i];
            operations += diff;
            a[i] = a[i-1] + 1;
        }
    }
    cout << operations << "\n";
    return 0;
}