#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
const int N = 5e5+7;
int n, a[N];
vector<int> occ[N];
struct ST {
int n;
vector<pair<int, int>> t;
vector<int> lazy;
void init(int nn) {
n = nn;
t.assign(4 * n + 5, {0, 0});
lazy.assign(4 * n + 5, 0);
}
pair<int, int> join(pair<int, int> a, pair<int, int> b) {
pair<int, int> c;
c.first = min(a.first, b.first);
c.second = max(a.second, b.second);
return c;
}
void push(int v, int tl, int tr) {
if (tl < tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
t[v].first += lazy[v];
t[v].second += lazy[v];
lazy[v] = 0;
}
void add(int v, int tl, int tr, int l, int r, int x) {
push(v, tl, tr);
if (l > tr || r < tl) return;
if (l <= tl && tr <= r) {
lazy[v] += x, push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
add(2 * v, tl, tm, l, r, x);
add(2 * v + 1, tm + 1, tr, l, r, x);
t[v] = join(t[2 * v], t[2 * v + 1]);
}
void add(int l, int r, int x) {
add(1, 1, n + 1, l + 1, r + 1, x);
}
pair<int, int> get(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if (l > tr || r < tl) return {1e9, -1e9};
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2;
return join(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
}
int get_min(int l, int r) {
return get(1, 1, n+1, l+1, r+1).first;
}
int get_max(int l, int r) {
return get(1, 1, n+1, l+1, r+1).second;
}
pair<int, int> get(int l, int r) {
return get(1, 1, n+1, l+1, r+1);
}
void clr() {
for (int i = 1; i <= 4 * n + 4; ++i) t[i] = {0, 0}, lazy[i] = 0;
}
};
ST t;
bool intersect(pair<int, int> a, pair<int, int> b) {
if (a.second < b.first || a.first > b.second) return false;
return true;
}
int sequence(int N, vector<int> A) {
n = N;
for (int i = 1; i <= n; ++i) a[i] = A[i - 1];
for (int i = 1; i <= n; ++i) occ[a[i]].push_back(i);
t.init(n);
vector<pair<int, int>> pr(n + 1), sf(n + 1);
vector<pair<int, int>> pr2(n + 1), sf2(n + 1);
for (int i = 1; i <= n; ++i) t.add(i, n, 1);
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (occ[i].empty()) continue;
for (auto j : occ[i]) pr[j - 1] = t.get(0, j - 1);
for (auto j : occ[i]) sf[j] = t.get(j, n);
for (auto j : occ[i]) t.add(j, n, -2);
for (auto j : occ[i]) pr2[j - 1] = t.get(0, j - 1);
for (auto j : occ[i]) sf2[j] = t.get(j, n);
int l = 1, r = occ[i].size();
while (l <= r) {
int m = (l + r) / 2;
bool ok = 0;
for (int j = 0; j + m - 1 < occ[i].size(); ++j) {
int l = occ[i][j];
int r = occ[i][j + m - 1];
pair<int, int> a = pr[l - 1];
pair<int, int> b = sf[r];
pair<int, int> c = pr2[l - 1];
pair<int, int> d = sf2[r];
if (a.first <= b.second && b.first <= a.second) {
ok = 1;
break;
}
if (c.first <= d.second && d.first <= c.second) {
ok = 1;
break;
}
if (a.second <= b.first && d.second <= c.first) {
ok = 1;
break;
}
if (b.second <= a.first && c.second <= d.first) {
ok = 1;
break;
}
}
if (ok == 1) l = m + 1;
if (ok == 0) r = m - 1;
}
ckmax(ans, l - 1);
}
return ans;
}
