#include <stdio.h>
#include <string.h>
#define N 8000
#define M (N * 4)
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ll[M], rr[M], xx[M], yy[M];
int compare_y(int h1, int h2) {
return yy[h2] - yy[h1];
}
int compare_r(int h1, int h2) {
return rr[h2] - rr[h1];
}
int (*compare)(int, int);
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(hh[j], h);
if (c == 0)
j++;
else if (c < 0) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
}
sort(hh, l, i);
l = k;
}
}
int ft[N * 2 + 1];
void update(int i, int n, int x) {
while (i < n) {
ft[i] = min(ft[i], x);
i |= i + 1;
}
}
int query(int i) {
int x = INF;
while (i >= 0) {
x = min(x, ft[i]);
i &= i + 1, i--;
}
return x;
}
int main() {
static int aa[N], ii[N], hh[M], jj[2][2][N], tt[N];
int n, m, k, h, h_, i, j, a, u, v, l, x, tmp;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &aa[i]), aa[i]--;
ii[aa[i]] = i;
}
m = 0;
ll[m] = 0, rr[m] = n - 1, xx[m] = 0, yy[m] = n - 1, m++;
k = 0;
while (1) {
for (u = 0; u < 2; u++) {
for (h = 0; h < m; h++)
hh[h] = h;
for (v = 0; v < 2; v++) {
memset(jj[u][v], 0x3f, n * sizeof *jj[u][v]);
compare = compare_y, sort(hh, 0, m);
memset(ft, 0x3f, (n * 2 + 1) * sizeof *ft);
for (a = n - 1, h = 0; a >= 0; a--) {
while (h < m && yy[h_ = hh[h]] >= a)
update(yy[h_] - rr[h_] + n, n * 2 + 1, ll[h_]), h++;
l = query(a - ii[a] + n);
if (l != INF)
jj[u][v][ii[a]] = min(jj[u][v][ii[a]], l);
}
compare = compare_r, sort(hh, 0, m);
memset(ft, 0x3f, (n * 2 + 1) * sizeof *ft);
for (i = n - 1, h = 0; i >= 0; i--) {
while (h < m && rr[h_ = hh[h]] >= i)
update(rr[h_] - yy[h_] + n, n * 2 + 1, xx[h_]), h++;
x = query(i - aa[i] + n);
if (x != INF)
jj[u][v][i] = min(jj[u][v][i], -aa[i] + i + x);
}
for (i = 0; i < n; i++) {
aa[i] = n - 1 - aa[i];
ii[aa[i]] = i;
}
for (h = 0; h < m; h++)
tmp = n - 1 - xx[h], xx[h] = n - 1 - yy[h], yy[h] = tmp;
}
for (a = 0; a < n; a++) {
ii[a] = n - 1 - ii[a];
aa[ii[a]] = a;
}
for (h = 0; h < m; h++)
tmp = n - 1 - ll[h], ll[h] = n - 1 - rr[h], rr[h] = tmp;
}
for (v = 0; v < 2; v++) {
for (i = 0; i < n; i++)
tt[i] = jj[1][v][n - 1 - i] == INF ? -INF : n - 1 - jj[1][v][n - 1 - i];
memcpy(jj[1][v], tt, n * sizeof *tt);
}
m = 0;
for (i = 0; i < n; i++) {
if ((j = jj[0][0][i]) <= i)
ll[m] = j, rr[m] = i - 1, xx[m] = aa[i] - i + j, yy[m] = aa[i] - 1, m++;
if ((j = jj[0][1][i]) <= i)
ll[m] = j, rr[m] = i - 1, xx[m] = aa[i] + 1, yy[m] = aa[i] + i - j, m++;
if ((j = jj[1][0][i]) >= i)
ll[m] = i + 1, rr[m] = j, xx[m] = aa[i] - j + i, yy[m] = aa[i] - 1, m++;
if ((j = jj[1][1][i]) >= i)
ll[m] = i + 1, rr[m] = j, xx[m] = aa[i] + 1, yy[m] = aa[i] + j - i, m++;
}
if (m == 0) {
printf("%d\n", n - k);
return 0;
}
k++;
}
return 0;
}
