#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<pair<int,int>,pair<int,int>>kwad;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=8007, INF=1e9+7;
int P[LIM], tr[4*LIM], N=1, n;
pair<int,int>K[LIM];
void upd(int v, int x) {
v+=N;
while(v) {
tr[v]=min(tr[v], x);
v/=2;
}
}
int cnt(int l, int r) {
if(l>r) return INF;
l+=N; r+=N;
int ans=min(tr[l], tr[r]);
while(l/2!=r/2) {
if(l%2==0) ans=min(ans, tr[l+1]);
if(r%2==1) ans=min(ans, tr[r-1]);
l/=2; r/=2;
}
return ans;
}
pair<int,int>obr(pair<int,int>x) {
return {n-1-x.nd, x.st};
}
kwad obrk(kwad x) {
x={obr(x.st), obr(x.nd)};
if(x.st.st>x.nd.st) swap(x.st.st, x.nd.st);
if(x.st.nd>x.nd.nd) swap(x.st.nd, x.nd.nd);
return x;
}
vector<kwad>solve(vector<kwad>T) {
vector<kwad>V;
rep(i, n) K[i]={i, P[i]};
rep(xd, 4) {
vector<int>mi(n, INF);
vector<pair<int,int>>S;
rep(i, n) S.pb({K[i].st-K[i].nd, -i-1});
rep(i, T.size()) S.pb({T[i].st.st-T[i].st.nd, i+1});
sort(all(S));
reverse(all(S));
rep(i, 2*N) tr[i]=INF;
for(auto i : S) {
int p=abs(i.nd)-1;
if(i.nd<0) mi[p]=min(mi[p], cnt(K[p].nd+1, n-1)-K[p].st);
else upd(T[p].st.nd, T[p].nd.st);
}
reverse(all(S));
rep(i, 2*N) tr[i]=INF;
for(auto i : S) {
int p=abs(i.nd)-1;
if(i.nd<0) mi[p]=min(mi[p], cnt(K[p].st+1, n-1)-K[p].nd);
else upd(T[p].st.st, T[p].nd.nd);
}
rep(i, n) if(K[i].st+mi[i]<n && K[i].nd+mi[i]<n) V.pb({K[i], {K[i].st+mi[i], K[i].nd+mi[i]}});
rep(i, n) K[i]=obr(K[i]);
rep(i, T.size()) T[i]=obrk(T[i]);
rep(i, V.size()) V[i]=obrk(V[i]);
}
return V;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
while(N<n) N*=2;
rep(i, n) {
cin >> P[i];
--P[i];
}
int ans=n;
vector<kwad>T;
rep(i, n) T.pb({{i, P[i]}, {i, P[i]}});
while(T.size()) {
--ans;
T=solve(T);
}
cout << ans << '\n';
}
