#include <bits/stdc++.h>
using namespace std;
const int N = 510000;
const int INF = (int)(2e9);
struct segtree {
vector<int> mn, mx, cc;
segtree(int n) {
mn = mx = cc = vector<int>(4 * n + 1, 0);
}
void merge(int v) {
mn[v] = min(mn[v * 2 + 0], mn[v * 2 + 1]) + cc[v];
mx[v] = max(mx[v * 2 + 0], mx[v * 2 + 1]) + cc[v];
}
void upd(int v, int l, int r, int ql, int qr, int x) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
cc[v] += x;
mn[v] += x;
mx[v] += x;
return;
}
int mid = (l + r) / 2;
upd(v * 2 + 0, l, mid, ql, qr, x);
upd(v * 2 + 1, mid + 1, r, ql, qr, x);
merge(v);
}
int get_min(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return INF;
if (ql <= l && r <= qr) return mn[v];
int mid = (l + r) / 2;
return min(get_min(v * 2 + 0, l, mid, ql, qr), get_min(v * 2 + 1, mid + 1, r, ql, qr)) + cc[v];
}
int get_max(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return -INF;
if (ql <= l && r <= qr) return mx[v];
int mid = (l + r) / 2;
return max(get_max(v * 2 + 0, l, mid, ql, qr), get_max(v * 2 + 1, mid + 1, r, ql, qr)) + cc[v];
}
};
vector<int> pos[N];
int sequence(int N, vector<int> A) {
int ans = 0;
reverse(begin(A), end(A));
A.push_back(0);
reverse(begin(A), end(A));
for (int i = 1; i <= N; i++)
pos[A[i]].push_back(i);
segtree cur(N + 1);
for (int i = 1; i <= N; i++)
cur.upd(1, 0, N, i, N, 1);
for (int i = 1; i <= N; i++) {
for (int k : pos[i - 0]) cur.upd(1, 0, N, k, N, -1);
for (int k : pos[i - 1]) cur.upd(1, 0, N, k, N, -1);
vector<array<int, 2>> base;
pos[i].push_back(N + 1);
int ptr = 0;
for (int k : pos[i]) {
base.push_back({cur.get_min(1, 0, N, ptr, k - 1), cur.get_max(1, 0, N, ptr, k - 1)});
ptr = k;
}
pos[i].pop_back();
int m = base.size();
vector<array<int, 2>> pref = base, suff = base;
for (int i = 1; i < m; i++) {
pref[i][0] = min(pref[i][0], pref[i - 1][0] - 1);
pref[i][1] = max(pref[i][1], pref[i - 1][1] + 1);
}
for (int i = m - 2; i >= 0; i--) {
suff[i][0] = min(suff[i][0], suff[i + 1][0] - 1);
suff[i][1] = max(suff[i][1], suff[i + 1][1] + 1);
}
ptr = 0;
for (int l = 0; l < m; l++) {
while (ptr + 1 < m) {
int len = ptr + 1 - l;
int lp = max(pref[l][0], suff[ptr + 1][0] - len);
int rp = min(pref[l][1], suff[ptr + 1][1] + len);
if (lp > rp) break;
ptr++;
}
ans = max(ans, ptr - l);
}
}
return ans;
}
/*
#include <cassert>
#include <cstdio>
#include <vector>
int32_t main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> A(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &A[i]));
}
int result = sequence(N, A);
printf("%d\n", result);
return 0;
}
//*/
