#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5,B=1000;
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
int a[n+1];
for(int i=1;i<=n;i++)cin>>a[i];
int dpl[n+1];dpl[1]=0;
for(int i=2;i<=n;i++)dpl[i]=dpl[i-1]+(a[i-1]-a[i]>=0?a[i-1]-a[i]+1:0);
int dpr[n+2]={0};dpr[n]=0;
for(int i=n-1;i>=1;i--)dpr[i]=dpr[i+1]+(a[i+1]-a[i]>=0?a[i+1]-a[i]+1:0);
int ans=2e9;
for(int i=1;i<=n;i++)ans=min(ans,max(dpl[i],dpr[i]));
int now[n+1];
for(int i=1;i<=n;i++)now[i]=a[i];
dpr[n]=0;int cur=n-2,add=0;
queue<pii>q;
for(int i=n-1;i>=1;i--){
while(!q.empty()&&q.front().f>i)add-=q.front().s,q.pop();
now[i]+=add;
dpr[i]=dpr[i+1]+max(now[i+1]-now[i]+1,0);
int tt=max(now[i+1]-now[i]+1,0);
now[i]+=tt;
while(cur>0&&now[cur]<=now[i])q.push({cur--,tt});
}
for(int i=1;i<=n-1;i++)ans=min(ans,dpl[i]+dpr[i+1]+max(now[i+1]-a[i]-dpl[i]+1,0));
cout<<ans;
}
