JOI: Harvest

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 2e5 + 5;

int arr[N];
lli qs1[N], qs2[N];

int main(){

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &arr[i]);
    }
    for(int i = 1; i <= n; ++i){
        int x = max(0, arr[i - 1] - arr[i] + 1);
        qs1[i] = qs1[i - 1] + x;
    }
    for(int i = n; i >= 1; --i){
        int x = max(0, arr[i + 1] - arr[i] + 1);
        qs2[i] = qs2[i + 1] + x;
    }
    lli mn = 1e18;
    for(int i = 1; i <= n; ++i){
        mn = min(mn, max(qs1[i], qs2[i]));
    }
    cout << mn;

    return 0;
}