#include<bits/stdc++.h>
using namespace std;
#ifndef BADGNU
#pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=8005;
const int M=5001;
const int B=447;
const int mod=998244353;
const ll INF=1e9;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;
struct ki{
int x,y,w;
ki():x(0),y(0),w(0){}
ki(int _x,int _y,int _w):x(_x),y(_y),w(_w){}
};
struct BIT{
int sz;
vector<int>f;
BIT():sz(0),f(vector<int>()){}
BIT(int n){
sz=1;
while(sz<n){
sz*=2ll;
}
f=vector<int>(sz*2,INF*2);
}
void clean(){
for(int i=0;i<sz*2;i++){
f[i]=INF*2;
}
}
void upd(int l,int x){
l+=sz;
f[l]=min(f[l],x);
while(l>1){
l>>=1;
f[l]=min(f[l*2],f[l*2+1]);
}
}
int get(int l,int r){
int res=INF*2;
l+=sz;
r+=sz;
while(l!=r){
if(l&1)res=min(res,f[l++]);
if(r&1)res=min(res,f[--r]);
l>>=1;
r>>=1;
}
return res;
}
};
int n,m;
int p[N];
int dp[4][N];
vector<int>p1,p2;
void test(){
cin>>n;
for(int i=0;i<n;i++){
cin>>p[i];
p[i]--;
p1.push_back(i);
p2.push_back(i);
}
sort(p1.begin(),p1.end(),[](int x,int y){
return x-p[x]<y-p[y];
});
sort(p2.begin(),p2.end(),[](int x,int y){
return x+p[x]<y+p[y];
});
int ans=n-1;
BIT st1(n),st2(n);
while(ans>=1){
vector<ki>v,v1,v2;
for(int mask=0;mask<4;mask++){
for(int i=0;i<n;i++){
if(dp[mask][i]!=INF){
int x=i-(mask&2?dp[mask][i]:0);
int y=p[i]-(mask&1?dp[mask][i]:0);
v.push_back({x,y,dp[mask][i]});
}
dp[mask][i]=INF;
}
}
v1=v;
v2=v;
m=v.size();
sort(v1.begin(),v1.end(),[](const ki&a,const ki&b){
return a.x-a.y<b.x-b.y;
});
sort(v2.begin(),v2.end(),[](const ki&a,const ki&b){
return a.x+a.y+a.w<b.x+b.y+b.w;
});
int posp=0,posv=0;
// i hate conditions
st1.clean();
st2.clean();
posp=0;
posv=0;
while(posp!=n||posv!=m){
int px=p1[posp],py=p[px];
int res1=(posp!=n?px-py:INF);
int res2=(posv!=m?v1[posv].x-v1[posv].y:INF);
if(res1>=res2){
st1.upd(v1[posv].x,v1[posv].y+v1[posv].w);
st2.upd(v1[posv].y+v1[posv].w,-v1[posv].x);
posv++;
}
else{
dp[0][px]=min(dp[0][px],st1.get(px+1,n)-py);
dp[3][px]=min(dp[3][px],px-(-st2.get(0,py)));
posp++;
}
}
// still hating
st1.clean();
st2.clean();
posp=n-1;
posv=m-1;
while(posp!=-1||posv!=-1){
int px=p1[posp],py=p[px];
int res1=(posp!=-1?px-py:-INF);
int res2=(posv!=-1?v1[posv].x-v1[posv].y:-INF);
if(res1<=res2){
st1.upd(v1[posv].y,v1[posv].x+v1[posv].w);
st2.upd(v1[posv].x+v1[posv].w,-v1[posv].y);
posv--;
}
else{
dp[0][px]=min(dp[0][px],st1.get(py+1,n)-px);
dp[3][px]=min(dp[3][px],py-(-st2.get(0,px)));
posp--;
}
}
//wtf author
st1.clean();
st2.clean();
posp=0;
posv=0;
while(posp!=n||posv!=m){
int px=p2[posp],py=p[px];
int res1=(posp!=n?px+py:INF);
int res2=(posv!=m?v2[posv].x+v2[posv].y+v2[posv].w:INF);
if(res1>=res2){
st1.upd(v2[posv].x,-v2[posv].y);
st2.upd(v2[posv].y,-v2[posv].x);
posv++;
}
else{
dp[1][px]=min(dp[1][px],py-(-st1.get(px+1,n)));
dp[2][px]=min(dp[2][px],px-(-st2.get(py+1,n)));
posp++;
}
}
// blyaaaaaaaaaaaaa
st1.clean();
st2.clean();
posp=n-1;
posv=m-1;
while(posp!=-1||posv!=-1){
int px=p2[posp],py=p[px];
int res1=(posp!=-1?px+py:-INF);
int res2=(posv!=-1?v2[posv].x+v2[posv].y+v2[posv].w:-INF);
if(res1<=res2){
st1.upd(v2[posv].y+v2[posv].w,v2[posv].x+v2[posv].w);
st2.upd(v2[posv].x+v2[posv].w,v2[posv].y+v2[posv].w);
posv--;
}
else{
dp[1][px]=min(dp[1][px],st1.get(0,py)-px);
dp[2][px]=min(dp[2][px],st2.get(0,px)-py);
posp--;
}
}
bool ok=1;
for(int mask=0;mask<4;mask++){
for(int i=0;i<n;i++){
int lx=(mask&2?i:n-i-1);
int rx=(mask&1?p[i]:n-p[i]-1);
if(dp[mask][i]>min(lx,rx)){
dp[mask][i]=INF;
}
if(dp[mask][i]!=INF){
ok=0;
}
}
}
if(ok){
break;
}
ans--;
}
cout<<ans<<'\n';
}
/*
*/
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// cout.tie(nullptr);
int t2=1;
// cin>>t2;
for(int i=1;i<=t2;i++){
test();
}
}
