#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
vector<int> a(n), pref(n), pc(n);
vector<int> suff(n), sc(n);
for(int i=0;i<n;i++) cin>>a[i];
int v = a[0], add = 0;
for(int i=1;i<n;i++){
pref[i] = pref[i-1];
if(a[i] > v){
add = 0;
} else {
if(add < v + 1 - a[i]){
pref[i] += ((v + 1) - a[i] - add);
} add = v + 1 - a[i];
}
v = max(v + 1, a[i]);
pc[i] = add;
}
v = a[n-1], add = 0;
for(int i=n-2;~i;i--){
suff[i] = suff[i+1];
if(a[i] > v){
add = 0;
} else {
if(add < v + 1 - a[i]){
suff[i] += ((v + 1) - a[i] - add);
} add = v + 1 - a[i];
}
v = max(v + 1, a[i]);
sc[i] = add;
}
int res = 1e18;
for(int i=0;i<n;i++){
res = min(res, max(pref[i], suff[i]));
//~ res = min(res, pref[i] + suff[i] - min(pc[i], sc[i]));
}
//~ for(int i=0;i<n;i++){
//~ cout<<pref[i]<<" ";
//~ } cout<<"\n";
//~ for(int i=0;i<n;i++){
//~ cout<<suff[i]<<" ";
//~ } cout<<"\n";
//~ for(int i=0;i<n;i++){
//~ cout<<pc[i]<<" ";
//~ } cout<<"\n";
//~ for(int i=0;i<n;i++){
//~ cout<<sc[i]<<" ";
//~ } cout<<"\n";
cout<<res<<"\n";
}
