#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];
int pref[N];
int min_pref[N], max_pref[N];
int min_suff[N], max_suff[N];
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) {
for (int i = 1; i <= n; ++i) {
if (occ[i].empty()) continue;
for (int j = 1; j <= n; ++j) pref[j] = 0;
for (int j = 1; j <= n; ++j) {
if (a[j] < i) pref[j] = -1;
if (a[j] > i) pref[j] = 1;
}
for (int j = 1; j <= n; ++j) pref[j] += pref[j - 1];
min_suff[n + 1] = 1e9, max_suff[n + 1] = -1e9;
for (int j = 1; j <= n; ++j) min_pref[j] = min(min_pref[j - 1], pref[j]);
for (int j = 1; j <= n; ++j) max_pref[j] = max(max_pref[j - 1], pref[j]);
for (int j = n; j >= 1; --j) min_suff[j] = min(min_suff[j + 1], pref[j]);
for (int j = n; j >= 1; --j) max_suff[j] = max(max_suff[j + 1], pref[j]);
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 = {min_pref[l - 1], max_pref[l - 1]};
pair<int, int> rgh = {min_suff[r] - x, max_suff[r] + x};
if (intersect(lft, rgh)) {
return true;
}
}
}
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;
}
