#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;
ST(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, l+1, r+1).first;
}
int get_max(int l, int r) {
return get(1, 1, n, l+1, r+1).second;
}
};
bool intersect(pair<int, int> a, pair<int, int> b) {
if (a.second < b.first || a.first > b.second) return false;
return true;
}
bool check(int x) {
ST t(n);
for (int i = 1; i <= n; ++i) t.add(i, n, 1);
for (int i = 1; i <= n; ++i) {
if (occ[i].empty()) continue;
for (auto j : occ[i]) t.add(j, n, -1);
for (int j = 0; j + x - 1 < occ[i].size(); ++j) {
int l = occ[i][j];
int r = occ[i][j + x - 1];
pair<int, int> lft = {t.get_min(0, l - 1), t.get_max(0, l - 1)};
pair<int, int> rgh = {t.get_min(r, n) - x, t.get_max(r, n) + x};
if (intersect(lft, rgh)) {
return true;
}
}
for (auto j : occ[i]) t.add(j, n, -1);
}
return false;
}
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);
int l = 1, r = n;
while (l <= r) {
int m = (l + r) / 2;
if (check(m)) {
l = m + 1;
} else {
r = m - 1;
}
}
return l - 1;
}
