#include<bits/stdc++.h>
#include<string.h>
#include <algorithm>
#include <stdlib.h>
#define ll long long
using namespace std;
ll k[300006],a,b,c,d,e,f,m[300006],i,j,n,h,g,l,r,ka,p,q[200005],t[200005];
map<ll,ll> maa,mii,mee;
vector<ll> vas[25],vis,vii;
int main(){
cin>>a;
for(i=0 ; i<a ; i++){
cin>>k[i];
}
h=1;
for(i=1 ; i<a ; i++){
if(k[i]<=k[i-1]){
t[i]=k[i-1]-k[i]+1;
}
else{
t[i]=0;
}
}
g=0;
h=1;
for(i=a-2 ; i>=0 ; i--){
if(k[i+1]>=k[i]){
m[i]=k[i+1]-k[i]+1;
}
else{
m[i]=0;
}
g+=m[i];
}
h=10000000000000000;
l=0;
for(i=0 ; i<a ; i++){
if(max(l+t[i],g)<h){
r=i;
h=max(l+t[i],g);
}
g-=m[i];
l+=t[i];
}
g=0;
cout<<h<<endl;
}
