#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 8005, inf = 1e9;
int n, p[N], rp[N], ans;
int f[N][4], g[N][4];
struct tree1{
	int a[N * 2];
	void init(){
		for (int i = 1; i <= n * 2; i++) a[i] = inf;
	}
	void add(int x, int k){
		for (; x <= n * 2; x += x & -x) a[x] = min(k, a[x]);
	}
	int ask(int x){
		int res = inf;
		for (; x; x -= x & -x) res = min(a[x], res);
		return res;
	}
}T1;
struct tree2{
	int a[N * 2];
	void init(){
		for (int i = 1; i <= n * 2; i++) a[i] = inf;
	}
	void add(int x, int k){
		for (; x; x -= x & -x) a[x] = min(k, a[x]);
	}
	int ask(int x){
		int res = inf;
		for (; x <= n * 2; x += x & -x) res = min(a[x], res);
		return res;
	}
}T2;
vector<pair<int, int>> ad[8][N];
void add(int l, int r, int y){
	ad[0][r].emplace_back(y - l + n, -y);
	ad[1][y + r - l].emplace_back(y - l + n, -l);
	ad[2][l].emplace_back(y + r, -y);
	ad[3][y + r - l].emplace_back(y + r, r);
	ad[4][l].emplace_back(y - l + n, y + r - l);
	ad[5][y].emplace_back(y - l + n, r);
	ad[6][r].emplace_back(y + r, y + r - l);
	ad[7][y].emplace_back(y + r, -l);
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout); 
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> p[i];
		rp[p[i]] = i;
	}
	ans = 1;
	while (1){
		for (int i = 0; i < 8; i++)
			for (int j = 1; j <= n; j++)
				ad[i][j].clear();
		memset(g, 0x3f, sizeof(g));
		for (int i = 1; i <= n; i++){
			if (f[i][0] <= min(n - i, n - p[i])) add(i, i + f[i][0], p[i]);
			if (f[i][1] <= min(i - 1, n - p[i])) add(i - f[i][1], i, p[i]);
			if (f[i][2] <= min(i - 1, p[i] - 1)) add(i - f[i][2], i, p[i] - f[i][2]);
			if (f[i][3] <= min(n - i, p[i] - 1)) add(i, i + f[i][3], p[i] - f[i][3]);
		}
		T1.init();
		for (int i = 1; i <= n; i++){
			g[i][2] = min(T1.ask(p[i] - i + n) + p[i], g[i][2]);
			for (pair<int, int> p : ad[0][i]) T1.add(p.first, p.second);
		}
		T2.init();
		for (int i = 1; i <= n; i++){
			g[rp[i]][2] = min(T2.ask(i - rp[i] + n) + rp[i], g[rp[i]][2]);
			for (pair<int, int> p : ad[1][i]) T2.add(p.first, p.second);
		}
		T1.init();
		for (int i = n; i >= 1; i--){
			g[i][3] = min(T1.ask(i + p[i]) + p[i], g[i][3]);
			for (pair<int, int> p : ad[2][i]) T1.add(p.first, p.second);
		}
		T2.init();
		for (int i = 1; i <= n; i++){
			g[rp[i]][3] = min(T2.ask(rp[i] + i) - rp[i], g[rp[i]][3]);
			for (pair<int, int> p : ad[3][i]) T2.add(p.first, p.second);
		}
		T2.init();
		for (int i = n; i >= 1; i--){
			g[i][0] = min(T2.ask(p[i] - i + n) - p[i], g[i][0]);
			for (pair<int, int> p : ad[4][i]) T2.add(p.first, p.second);
		}
		T1.init();
		for (int i = n; i >= 1; i--){
			g[rp[i]][0] = min(T1.ask(i - rp[i] + n) - rp[i], g[rp[i]][0]);
			for (pair<int, int> p : ad[5][i]) T1.add(p.first, p.second);
		}
		T2.init();
		for (int i = 1; i <= n; i++){
			g[i][1] = min(T2.ask(i + p[i]) - p[i], g[i][1]);
			for (pair<int, int> p : ad[6][i]) T2.add(p.first, p.second);
		}
		T1.init();
		for (int i = n; i >= 1; i--){
			g[rp[i]][1] = min(T1.ask(rp[i] + i) + rp[i], g[rp[i]][1]);
			for (pair<int, int> p : ad[7][i]) T1.add(p.first, p.second);
		}
		bool flg = 0;
		for (int i = 1; i <= n; i++){
			if (g[i][0] <= min(n - i, n - p[i])) flg = 1;
			if (g[i][1] <= min(i - 1, n - p[i])) flg = 1;
			if (g[i][2] <= min(i - 1, p[i] - 1)) flg = 1;
			if (g[i][3] <= min(n - i, p[i] - 1)) flg = 1;
		}
		if (flg) ans++;
		else break;
		memcpy(f, g, sizeof(f));
	}
	cout << n - ans;
	return 0;
}