#include <bits/stdc++.h>
//#include "sequence.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
const int N = 5e5 + 5;
const int NN = N * 4;
int a[N], n;
vector <int> idx[N];
ll mx[NN], mn[NN], st[NN], gosh[NN], jogg;
void build (int ind, int l, int r) {
if (l == r) {
st[ind] = mn[ind] = mx[ind] = l;
return;
}
int mid = (l + r) / 2;
build (ind * 2, l, mid);
build (ind * 2 + 1, mid + 1, r);
mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]);
mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]);
}
void update (int ind, int l, int r, int x, int y, ll val) {
if (gosh[ind / 2]) {
gosh[ind] += gosh[ind / 2];
st[ind] += (r - l + 1) * gosh[ind / 2];
mn[ind] += gosh[ind / 2];
mx[ind] += gosh[ind / 2];
}
if (x > r or l > y) {
return;
}
if (x <= l and r <= y) {
gosh[ind] += val;
st[ind] += (r - l + 1) * val;
mn[ind] += val;
mx[ind] += val;
return;
}
int mid = (l + r) / 2;
update (ind * 2, l, mid, x, y, val);
update (ind * 2 + 1, mid + 1, r, x, y, val);
gosh[ind] = 0;
st[ind] = st[ind * 2] + st[ind * 2 + 1];
mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]);
mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]);
}
void uly (int ind, int l, int r, int x, int y) {
if (gosh[ind / 2]) {
gosh[ind] += gosh[ind / 2];
st[ind] += (r - l + 1) * gosh[ind / 2];
mn[ind] += gosh[ind / 2];
mx[ind] += gosh[ind / 2];
}
if (x > r or l > y) {
return;
}
if (x <= l and r <= y) {
jogg = max (jogg, mx[ind]);
return;
}
int mid = (l + r) / 2;
uly (ind * 2, l, mid, x, y);
uly (ind * 2 + 1, mid + 1, r, x, y);
gosh[ind] = 0;
st[ind] = st[ind * 2] + st[ind * 2 + 1];
mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]);
mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]);
}
void kici (int ind, int l, int r, int x, int y) {
if (gosh[ind / 2]) {
gosh[ind] += gosh[ind / 2];
st[ind] += (r - l + 1) * gosh[ind / 2];
mn[ind] += gosh[ind / 2];
mx[ind] += gosh[ind / 2];
}
if (x > r or l > y) {
return;
}
if (x <= l and r <= y) {
jogg = min (jogg, mn[ind]);
return;
}
int mid = (l + r) / 2;
kici (ind * 2, l, mid, x, y);
kici (ind * 2 + 1, mid + 1, r, x, y);
gosh[ind] = 0;
st[ind] = st[ind * 2] + st[ind * 2 + 1];
mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]);
mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]);
}
int sequence(int N, vector<int> A) {
n = N;
for (int i = 0; i < n; ++i) {
a[i] = A[i];
idx[a[i]].pb (i + 1);
}
// for (int pos : idx[1]) {
// cout << pos << " ";
// }
// exit(0);
int l = 2, r = n, jog = 1;
while (l <= r) {
int md = (l + r) / 2;
// md = 3;
// cout << md << "\n";
bool bolya = 0;
build (1, 1, n);
for (int i = 1; i <= n; ++i) {
gosh[i] = 0;
}
jogg = -1e18;
for (int i = 1; i <= n; ++i) {
for (int pos : idx[i]) {//suwagt value-sy 1 bolup dur 0 owurmeli
update (1, 1, n, pos, n, -1);
uly (1, 1, n, 9, 10);
// cout << jogg << "\n";
// exit(0);
}
for (int pos : idx[i - 1]) {// suwagt value-sy 0 bolup dur -1 owurmeli
update (1, 1, n, pos, n, -1);
}
for (int j = 0; j + md - 1 < (int)idx[i].sz; ++j) {
ll a1, a2, b1, b2;
//
jogg = -1e18;
uly (1, 1, n, idx[i][j + md - 1], n);
a2 = jogg;
jogg = 1e18;
kici(1, 1, n, idx[i][j + md - 1], n);
a1 = jogg;
jogg = -1e18;
uly (1, 1, n, 1, idx[i][j]);
b2 = jogg;
jogg = 1e18;
kici (1, 1, n, 1, idx[i][j]);
b1 = jogg;
if (b1 > 0) b1 = 0;
if (b2 < 0) b2 = 0;
// cout << "men\n";
// cout << a1 << " " << b1 << " " << a2 << "\n";
// cout << b1 << " " << a1 << " " << b2 << "\n";
// cout << "men " << idx[i][j] << " " << idx[i][j + md - 1] << " " << i;
// exit(0);
if ((a1 <= b1 and b1 <= a2) or (b1 <= a1 and a1 <= b2)) {
bolya = 1;
break;
}
int jj = max (a1, b1), jj1 = min(a2, b2);
if ((jj <= md + jj1)) {
bolya = 1;
// cout << "menj\n";
// cout << a1 << " " << b1 << " " << a2 << "\n";
// cout << b1 << " " << a1 << " " << b2 << "\n";
// cout << "menj " << idx[i][j] << " " << idx[i][j + md - 1] << " " << i;
// exit(0);
break;
}
}
if (bolya) break;
}
// cout << bolya << "\n";
// cout << "gutar\n";
// exit(0);
if (bolya) {
l = md + 1;
jog = md;
}
else {
r = md - 1;
}
}
return jog;
}
// a[i]>=1 and a[i] <= n
//int main() {
// freopen ("input.txt", "r", stdin);
// 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;
//}
/*
9
1 1 2 3 4 3 2 1 1
answer : 2
7
1 2 3 1 2 1 3
answer : 3
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
answer : 3
10
1 3 1 10 5 6 1 4 1 8
answer : 2
9
9 6 6 4 3 4 3 6 5
answer : 3
*/
