#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define ss second
#define ina insert
#define pb push_back
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
int x[n];
for(int i=0; i<n; i++){
cin>>x[i];
}
int pre[n];
fill(pre,pre+n,0);
int suf[n];
fill(suf,suf+n,0);
int pa[n];
fill(pa,pa+n,0);
int su[n];
fill(su,su+n,0);
for(int i=1; i<n; i++){
pre[i]=pre[i-1];
if(x[i]>x[i-1])continue;
int k=x[i-1]-x[i];
k++;
pa[i]=k;
pre[i]+=k;
}
for(int i=n-2; i>=0; i--){
suf[i]=suf[i+1];
if(x[i]>x[i+1])continue;
int k=x[i+1]-x[i];
k++;
su[i]=k;
suf[i]+=k;
}
int ans=1e18;
for(int i=0; i<n; i++){
// int bati=pre[i];
// int ixvi=0;
// if(i<n-1)ixvi=suf[i+1];
// int h=pa[i];
// int g=su[i];
// int ans1=bati+ixvi+max(h,g);
ans=min(ans,max(pre[i],suf[i]));
}
cout<<ans<<endl;
}
