#include "sequence.h"
#include <bits/extc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int32_t, int32_t>
#define tiii tuple <int32_t, int32_t, int32_t>
#define all(a) a.begin(), a.end()
using namespace std;
using namespace __gnu_pbds;
#define ordered_multiset tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
const int N = 5e5 + 5;
const int inf = 1e18;
int n, a[N], b[N];
struct lazyseg {
int lazy[4 * N], mnseg[4 * N], mxseg[4 * N];
void push(int l, int r, int i){
mnseg[i] += lazy[i];
mxseg[i] += lazy[i];
if (l != r) lazy[2 * i] += lazy[i], lazy[2 * i + 1] += lazy[i];
lazy[i] = 0;
}
void build(int l, int r, int i){
lazy[i] = 0;
if (l == r) return mnseg[i] = mxseg[i] = b[l], void();
int mid = (l + r) / 2;
build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
mnseg[i] = min(mnseg[2 * i], mnseg[2 * i + 1]);
mxseg[i] = max(mxseg[2 * i], mxseg[2 * i + 1]);
}
void update(int l, int r, int i, int ll, int rr, int val){
push(l, r, i);
if (l >= ll && r <= rr) return lazy[i] += val, push(l, r, i), void();
if (r < ll || l > rr) return;
int mid = (l + r) / 2;
update(l, mid, 2 * i, ll, rr, val);
update(mid + 1, r, 2 * i + 1, ll, rr, val);
mxseg[i] = max(mxseg[2 * i], mxseg[2 * i + 1]);
mnseg[i] = min(mnseg[2 * i], mnseg[2 * i + 1]);
}
int mnquery(int l, int r, int i, int ll, int rr){
push(l, r, i);
if (l >= ll && r <= rr) return mnseg[i];
if (r < ll || l > rr) return inf;
int mid = (l + r) / 2;
return min(mnquery(l, mid, 2 * i, ll, rr), mnquery(mid + 1, r, 2 * i + 1, ll, rr));
}
int mxquery(int l, int r, int i, int ll, int rr){
push(l, r, i);
if (l >= ll && r <= rr) return mxseg[i];
if (r < ll || l > rr) return -inf;
int mid = (l + r) / 2;
return max(mxquery(l, mid, 2 * i, ll, rr), mxquery(mid + 1, r, 2 * i + 1, ll, rr));
}
} seg;
int32_t sequence(int32_t Nn, vector<int32_t> A) {
n = Nn;
vector <int> mp[n + 1];
int mx = 0;
vector <int> freq(n + 1);
for (int i = 0; i < n; i++) {
a[i + 1] = A[i];
freq[A[i]]++;
b[i + 1] = 1 + b[i];
mp[a[i + 1]].emb(i + 1);
}
int val = 0, ans = 1;
seg.build(1, n, 1);
while (++val <= n) {
auto vec = mp[val];
for (auto idx : vec) seg.update(1, n, 1, idx, n, -1);
int l = ans + 1, r = vec.size();
while (l <= r) {
int mid = (l + r) / 2;
bool ok = 0;
for (int i = 0; i + mid - 1 < vec.size(); i++) {
int cur = i;
int nxt = i + mid - 1;
int lmn = min(0ll, (vec[cur] > 1 ? seg.mnquery(1, n, 1, 1, vec[cur]-1) : 0ll));
int lmx = max(0ll, (vec[cur] > 1 ? seg.mxquery(1, n, 1, 1, vec[cur]-1) : 0ll));
int rmn = seg.mnquery(1, n, 1, vec[nxt], n);
int rmx = seg.mxquery(1, n, 1, vec[nxt], n);
int mnsum = rmn - lmx;
int mxsum = rmx - lmn;
int mnwant = -mid;
int mxwant = mid;
if (!(mnsum > mxwant || mxsum < mnwant)) {
ok = 1;
break;
}
}
if (ok) ans = mid, l = mid + 1;
else r = mid - 1;
}
for (auto idx : vec) seg.update(1, n, 1, idx, n, -1);
}
return ans;
}
