#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define forn(i,a,b) for(int i = a; i<b; i++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
#ifdef D
#define debug(x) cout << x
#else
#define debug(x) //nothing
#endif
ll n;
/*
vector<pair<ll,pair<ll,ll>>> solve(vector<ll> v){
vector<pair<ll,pair<ll,ll>>> res(n);
ll rval=-1;
forn(i,0,n){
rval=max(rval+1, v[i]);
res[i].snd.fst=rval;
v[i]=rval-v[i];
}
ll pres = 0;
forn(i,0,n){
pres+=v[i];
res[i].fst=pres;
}
return res;
}*/
vector<pair<ll,pair<ll,ll>>> solve(vector<ll> v){
vector<pair<ll,pair<ll,ll>>> res(n);
ll rval=-1;
forn(i,0,n){
rval=max(rval+1, v[i]);
res[i].snd.fst=rval;
v[i]=rval-v[i];
}
ll pres = 0;
forn(i,0,n){
if(i-1>0 && v[i-1]>v[i]){
v[i]=0;
}
res[i].fst=pres+v[i];
res[i].snd.snd=pres;
if(i+1<n && v[i+1]>=v[i]){
v[i]=0;
}
pres+=v[i];
}
return res;
}
int main(){
cin>>n;
vector<ll> v(n); forn(i,0,n) cin>>v[i];
vector<pair<ll,pair<ll,ll>>> left = solve(v);
reverse(ALL(v));
vector<pair<ll,pair<ll,ll>>> right = solve(v);
reverse(ALL(right));
forn(i,0,n){
debug(" ("<<left[i].fst<<" "<<left[i].snd.fst<<" "<<left[i].snd.snd<<") ");
}debug("\n");
forn(i,0,n){
debug(" ("<<right[i].fst<<" "<<right[i].snd.fst<<" "<<right[i].snd.snd<<") ");
}debug("\n");
ll best = min(right[0].fst, left[n-1].fst);
forn(i,0,n-1){
ll aux = (left[i].snd.fst==right[i+1].snd.fst?1:0);
debug(left[i].fst<<" "<<right[i+1].fst<<" "<<aux<<'\n');
best=min(best,max(left[i].fst,right[i+1].fst)+aux);
debug(best<<'\n');
}
cout<<best<<'\n';
return 0;
}
