#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ans;
int oar[1000006];
int ar[1000006];
int par[1000006];
int sar[1000006];
int ps[1000006];
int sf[1000006];
int adp[200005];
int sfp[200005];
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>ar[i];
oar[i]=ar[i];
par[i]=ar[i];
sar[i]=ar[i];
}
for(int i=2;i<=n;i++){
ps[i]=ps[i-1];
if(par[i]<=par[i-1]){
par[i]=par[i-1]+1;
ps[i]+=max(0ll,ar[i-1]-ar[i]+1);
adp[i]=max(0ll,ar[i-1]-ar[i]+1);
}
}
for(int i=n-1;i>=1;i--){
sf[i]=sf[i+1];
if(sar[i]<=sar[i+1]){
sar[i]=sar[i+1]+1;
sf[i]+=max(0ll,ar[i+1]-ar[i]+1);
sfp[i]=max(0ll,ar[i+1]-ar[i]+1);
}
}
for(int i=1;i<=n;i++){
adp[i]=max(adp[i],adp[i-1]);
}
for(int i=n;i>=1;i--){
sfp[i]=max(sfp[i+1],sfp[i]);
}
ans=min(ps[n],sf[1]);
for(int i=2;i<=n;i++){
int cal=max(ps[i-1],sf[i]);
if(par[i-1]==sar[i]){
cal=max(ps[i-1]+1,sf[i]);
cal=min(cal,max(ps[i-1],sf[i]+1));
}
ans=min(ans,cal);
}
cout<<ans<<endl;
}
