#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
const ll N=1e6+5,INF=1e18;
ll a[N],p[N],s[N],y,z,t,x,n,q,mx,mn,k,ans,ind,m,l,r;
bool ok,okk;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
for (int i=1; i<=n; i++){
cin >> a[i];
}
p[1]=0;
for (int i=2; i<=n; i++){
p[i]=p[i-1];
x=max(0ll,a[i-1]-a[i]+1);
p[i]+=x;
}
s[n]=0;
for (int i=n-1; i>=1; i--){
s[i]=s[i+1];
x=max(0ll,a[i+1]-a[i]+1);
s[i]+=x;
}
ans=INF;
for (int i=1; i<=n; i++){
x=max(p[i],s[i]);
ans=min(ans,x);
}
cout<<ans<<endl;
}
