/*
100-POINT SOLUTION FOR "GIRAFFES" (JOI 2022 OPEN CONTEST)
- Solution: Speeding up dynamic programming with sweepline algorithm using segment tree
- Time Complexty: O(N log N * (N - answer)) (= O(N^1.5 log N) for average case)
*/
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class segtree {
private:
int sz;
std::vector<int> val;
public:
static const int INF = 2012345678;
segtree() : sz(0), val(std::vector<int>()) {};
segtree(int n) {
sz = 1;
while (sz < n) {
sz *= 2;
}
val = std::vector<int>(sz * 2, INF);
}
void reset() {
for (int i = 0; i < sz * 2; i++) {
val[i] = INF;
}
}
void upgrade(int pos, int x) {
pos += sz;
val[pos] = std::min(val[pos], x);
while (pos > 1) {
pos >>= 1;
val[pos] = std::min(val[pos * 2], val[pos * 2 + 1]);
}
}
int rangemin(int l, int r) {
l += sz;
r += sz;
int answer = INF;
while (l != r) {
if ((l & 1) == 1) answer = std::min(answer, val[l++]);
if ((r & 1) == 1) answer = std::min(answer, val[--r]);
l >>= 1;
r >>= 1;
}
return answer;
}
};
class square {
public:
int x, y, l;
square() : x(0), y(0), l(0) {};
square(int x_, int y_, int l_) : x(x_), y(y_), l(l_) {};
};
int solve(int N, const vector<int>& P) {
// dp[i][j]: smallest size of square of "answer = t" with point (j, P[j]) at direction i
const int INF = 1012345678;
vector<vector<int> > dp(4, vector<int>(N, 0));
int t = 1;
// step #0. preparation
vector<int> pa(N), pb(N);
for (int i = 0; i < N; i++) {
pa[i] = i;
pb[i] = i;
}
sort(pa.begin(), pa.end(), [&](int i, int j) { return i - P[i] < j - P[j]; });
sort(pb.begin(), pb.end(), [&](int i, int j) { return i + P[i] < j + P[j]; });
while (true) {
// step #1. enumerate all squares
vector<square> sq;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < N; j++) {
if (dp[i][j] != INF) {
int x = j - (i & 2 ? dp[i][j] : 0);
int y = P[j] - (i & 1 ? dp[i][j] : 0);
sq.push_back(square(x, y, dp[i][j]));
}
}
}
int S = sq.size();
// step #2. preparation
dp = vector<vector<int> >(4, vector<int>(N, INF));
vector<square> sqa = sq;
sort(sqa.begin(), sqa.end(), [](const square& s1, const square& s2) { return s1.x - s1.y < s2.x - s2.y; });
vector<square> sqb = sq;
sort(sqb.begin(), sqb.end(), [](const square& s1, const square& s2) { return s1.x + s1.y + s1.l < s2.x + s2.y + s2.l; });
segtree seg1(N);
segtree seg2(N);
int posp, possq;
// step #3. sweepline by increasing x-y
seg1.reset();
seg2.reset();
posp = 0;
possq = 0;
while (posp != N || possq != S) {
int px = pa[posp];
int py = P[pa[posp]];
int v1 = (posp != N ? px - py : INF);
int v2 = (possq != S ? sqa[possq].x - sqa[possq].y : INF);
if (v1 >= v2) {
seg1.upgrade(sqa[possq].x, sqa[possq].y + sqa[possq].l);
seg2.upgrade(sqa[possq].y + sqa[possq].l, -sqa[possq].x);
possq += 1;
}
else {
dp[0][px] = min(dp[0][px], seg1.rangemin(px + 1, N) - py);
dp[3][px] = min(dp[3][px], px - (-seg2.rangemin(0, py)));
posp += 1;
}
}
// step #4. sweepline by decreasing x-y
seg1.reset();
seg2.reset();
posp = N - 1;
possq = S - 1;
while (posp != -1 || possq != -1) {
int px = pa[posp];
int py = P[pa[posp]];
int v1 = (posp != -1 ? px - py : -INF);
int v2 = (possq != -1 ? sqa[possq].x - sqa[possq].y : -INF);
if (v1 <= v2) {
seg1.upgrade(sqa[possq].y, sqa[possq].x + sqa[possq].l);
seg2.upgrade(sqa[possq].x + sqa[possq].l, -sqa[possq].y);
possq -= 1;
}
else {
dp[0][px] = min(dp[0][px], seg1.rangemin(py + 1, N) - px);
dp[3][px] = min(dp[3][px], py - (-seg2.rangemin(0, px)));
posp -= 1;
}
}
// step #5. sweepline by increasing x+y
seg1.reset();
seg2.reset();
posp = 0;
possq = 0;
while (posp != N || possq != S) {
int px = pb[posp];
int py = P[pb[posp]];
int v1 = (posp != N ? px + py : INF);
int v2 = (possq != S ? sqb[possq].x + sqb[possq].y + sqb[possq].l : INF);
if (v1 >= v2) {
seg1.upgrade(sqb[possq].x, -sqb[possq].y);
seg2.upgrade(sqb[possq].y, -sqb[possq].x);
possq += 1;
}
else {
dp[1][px] = min(dp[1][px], py - (-seg1.rangemin(px + 1, N)));
dp[2][px] = min(dp[2][px], px - (-seg2.rangemin(py + 1, N)));
posp += 1;
}
}
// step #6. sweepline by decreasing x+y
seg1.reset();
seg2.reset();
posp = N - 1;
possq = S - 1;
while (posp != -1 || possq != -1) {
int px = pb[posp];
int py = P[pb[posp]];
int v1 = (posp != -1 ? px + py : -INF);
int v2 = (possq != -1 ? sqb[possq].x + sqb[possq].y + sqb[possq].l : -INF);
if (v1 <= v2) {
seg1.upgrade(sqb[possq].y + sqb[possq].l, sqb[possq].x + sqb[possq].l);
seg2.upgrade(sqb[possq].x + sqb[possq].l, sqb[possq].y + sqb[possq].l);
possq -= 1;
}
else {
dp[1][px] = min(dp[1][px], seg1.rangemin(0, py) - px);
dp[2][px] = min(dp[2][px], seg2.rangemin(0, px) - py);
posp -= 1;
}
}
// step #7. final cleanup
for (int i = 0; i < 4; i++) {
for (int j = 0; j < N; j++) {
int xlim = (i & 2 ? j : (N - 1) - j);
int ylim = (i & 1 ? P[j] : (N - 1) - P[j]);
if (dp[i][j] > min(xlim, ylim)) {
dp[i][j] = INF;
}
}
}
if (dp == vector<vector<int> >(4, vector<int>(N, INF))) {
break;
}
t += 1;
}
return N - t;
}
int main() {
int N;
cin >> N;
vector<int> P(N);
for (int i = 0; i < N; i++) {
cin >> P[i];
P[i] -= 1;
}
int answer = solve(N, P);
cout << answer << endl;
return 0;
}
