#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY 1000000005
#define mod 998244353
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mid (start+end)/2
#define lim 200005
#define se second
#define fi first
int dizi[lim],pre[lim],suf[lim],treep[4*lim],trees[4*lim];
inline void build1(int node,int start,int end){
if(start>end)return ;
if(start==end){
treep[node]=pre[start];
return ;
}
build1(node*2,start,mid),build1(node*2+1,mid+1,end);
treep[node]=max(treep[node*2],treep[node*2+1]);
return ;
}
inline void build2(int node,int start,int end){
if(start>end)return ;
if(start==end){
trees[node]=suf[start];
return ;
}
build2(node*2,start,mid),build2(node*2+1,mid+1,end);
trees[node]=max(trees[node*2],trees[node*2+1]);
return ;
}
inline int query1(int node,int start,int end,int l,int r){
if(start>end || start>r || end<l)return 0;
if(start>=l && end<=r)return treep[node];
return max(query1(node*2,start,mid,l,r),query1(node*2+1,mid+1,end,l,r));
}
inline int query2(int node,int start,int end,int l,int r){
if(start>end || start>r || end<l)return 0;
if(start>=l && end<=r)return trees[node];
return max(query2(node*2,start,mid,l,r),query2(node*2+1,mid+1,end,l,r));
}
int32_t main(){
faster
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>dizi[i];
int tut=dizi[1];
for(int i=2;i<=n;i++){
tut=max(tut+1,dizi[i]);
pre[i]=tut-dizi[i];
}
tut=dizi[n];
for(int i=n-1;i>=1;i--){
tut=max(tut+1,dizi[i]);
suf[i]=tut-dizi[i];
}
build1(1,1,n);
build2(1,1,n);
int cev=LLONG_MAX;
for(int i=1;i<=n;i++){
int tut1=query1(1,1,n,1,i);
int tut2=query2(1,1,n,i,n);
cev=min(cev,max(tut1,tut2));
}
cout<<cev<<'\n';
return 0;
}
