#include "sequence.h"
#include <bits/stdc++.h>
#define maxn 500005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int a[maxn], n;
vector<int> nho[maxn];
int stMin[4*maxn], stMax[4*maxn], lz[4*maxn];
void apply(int r, int d) {
stMin[r] += d;
stMax[r] += d;
lz[r] += d;
}
void down(int r) {
if (lz[r]) {
apply(r<<1, lz[r]);
apply(r<<1|1, lz[r]);
lz[r] = 0;
}
}
void up(int r) {
stMin[r] = min(stMin[r<<1], stMin[r<<1|1]);
stMax[r] = max(stMax[r<<1], stMax[r<<1|1]);
}
void update(int u, int v, int d, int r = 1, int lo = 0, int hi = n) {
if (u <= lo && hi <= v) {
apply(r, d);
return;
}
down(r);
int mid = (lo + hi) >> 1;
if (u <= mid) update(u, v, d, r<<1, lo, mid);
if (v > mid) update(u, v, d, r<<1|1, mid+1, hi);
up(r);
}
int getMin(int u, int v, int r = 1, int lo = 0, int hi = n) {
if (u <= lo && hi <= v) return stMin[r];
down(r);
int mid = (lo + hi) >> 1;
return min(u <= mid ? getMin(u, v, r<<1, lo, mid) : INT_MAX, v > mid ? getMin(u, v, r<<1|1, mid+1, hi) : INT_MAX);
}
int getMax(int u, int v, int r = 1, int lo = 0, int hi = n) {
if (u <= lo && hi <= v) return stMax[r];
down(r);
int mid = (lo + hi) >> 1;
return max(u <= mid ? getMax(u, v, r<<1, lo, mid) : INT_MIN, v > mid ? getMax(u, v, r<<1|1, mid+1, hi) : INT_MIN);
}
ii L[maxn], R[maxn];
int ok(int x) {
for (int o = 1; o <= n; o++) {
int sz = nho[o].size();
for (int i = 0; i <= sz-x; i++) {
int j = i+x-1;
ii A = L[nho[o][i]], B = R[nho[o][j]],
C = ii{max(B.fi-A.se, -x), min(B.se-A.fi, x)};
if (C.fi <= C.se) return 1;
}
}
return 0;
}
int mainProgram() {
for (int i = 1; i <= n; i++) nho[a[i]].emplace_back(i);
for (int i = 1; i <= n; i++) update(i, n, 1);
for (int o = 1; o <= n; o++) {
for (int i : nho[o]) update(i, n, -1);
for (int i : nho[o]) L[i] = ii{getMin(0, i-1), getMax(0, i-1)};
int sz = nho[o].size();
for (int i = sz-1; i >= 0; i--) {
int p = nho[o][i];
R[p].fi = getMin(p, n);
update(p, n, -1);
}
for (int i : nho[o]) update(i, n, 1);
for (int i = sz-1; i >= 0; i--) {
int p = nho[o][i];
R[p].se = getMax(p, n);
update(p, n, 1);
}
for (int i : nho[o]) update(i, n, -2);
}
int lo = 1, hi = n+1;
while (hi-lo>1) {
int mid = (lo+hi)>>1;
if (ok(mid)) lo = mid;
else hi = mid;
}
return lo;
}
int sequence(int N, vector<int> A) {
n = N;
for (int i = 0; i < N; i++) a[i+1] = A[i];
return mainProgram();
}
