#include "bits/stdc++.h"
using namespace std;
#define int long long
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n; cin>>n;
int a[n+5],b[n+5],d[n+5];
for(int i=1; i<=n; i++) cin>>a[i];
multiset<int> diff;
b[n] = a[n]; diff.insert(0); d[n]=0;
for(int i=n-1; i>0; i--){
b[i]=max({a[i],b[i+1]+1,a[i]+d[i+1]});
d[i]=b[i]-a[i];
//b[i]=max(a[i],b[i+1]+1);
diff.insert(d[i]);
}
b[n+1]=a[n+1]=a[n]-1; b[0]=a[0]=a[1]-1; d[0]=0; d[n+1]=0;
int an = *diff.rbegin();
//cout<<an<<endl;
//for(int i : diff) cout<<i<<' ';
//cout<<"HEY"<<endl;
for(int i=2; i<=n; i++){
//cout<<(*diff.rbegin())<<endl;
//shift peak
int prev = b[i-1]-a[i-1], cr = b[i]-a[i];
b[i-1] = max({a[i-1],b[i-2]+1,a[i-1]+d[i-2]});
/*if(i==5){
cout<<b[i-1]<<' '<<a[i-1]<<' '<<b[i-2]<<' '<<d[i-2]<<"P"<<endl;
}*/
d[i-1]=b[i-1]-a[i-1];
b[i] = max({a[i],b[i-1]+1,b[i+1]+1,a[i]+min(d[i-1],d[i+1])});
//b[i-1]=max(a[i-1],b[i-2]+1);
//b[i]=max({a[i],b[i-1]+1,b[i+1]+1});
diff.erase(diff.find(prev));
diff.erase(diff.find(cr));
d[i-1]=b[i-1]-a[i-1]; d[i]=b[i]-a[i];
diff.insert(d[i-1]);
diff.insert(d[i]);
an=min(an, *diff.rbegin());
}
cout<<an;
}
