#include <bits/stdc++.h>
using namespace std;
const int MM = 2e5+5;
int n,a[MM],pref[MM],suff[MM];
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int add = 0;
for(int i = 1; i <= n; i++){
if(i > 1 && a[i]+add <= a[i-1]+add){
add += a[i-1]+add+1 - (a[i]+add);
}
pref[i] = add;
}
add = 0;
for(int i = n; i >= 1; i--){
if(i < n && a[i]+add <= a[i+1]+add){
add += a[i+1]+add+1 - (a[i]+add);
}
suff[i] = add;
}
/*
for(int i = 1; i <= n; i++){
cout << pref[i] << " " << suff[i] << "\n";
}*/
int ans = min(suff[1],pref[n]);
for(int i = 2; i < n; i++){
int mx = max(suff[i+1],pref[i-1]);
int v = a[i] + mx;
int mxv = max(a[i-1]+pref[i-1],a[i+1]+suff[i+1]);
int off = max(0,(mxv+1) - v);
ans = min(ans,mx + off);
}
cout << ans << "\n";
}
// claim: we should only do operations that cross k
// proof: magic
// thus, we can consider left and right seperately, and the answer would be max (lans,rans)
