#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 <vector <int>> mp(n + 1);
for (int i = 0; i < n; i++) {
a[i + 1] = A[i];
b[i + 1] = 1 + b[i];
mp[A[i]].emplace_back(i + 1);
}
int val = 0, ans = 1;
seg.build(1, n, 1);
while (++val <= n) {
auto &vec = mp[val];
if (vec.empty()) continue;
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 = 0, lmx = 0;
if (vec[cur] > 1) {
lmn = min(0ll, seg.mnquery(1, n, 1, 1, vec[cur] - 1));
lmx = max(0ll, seg.mxquery(1, n, 1, 1, vec[cur] - 1));
}
int rmn = seg.mnquery(1, n, 1, vec[nxt], n);
int rmx = seg.mxquery(1, n, 1, vec[nxt], n);
if (rmn - lmx <= 2 * mid && rmx - lmn >= 0) {
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, -2);
}
return ans;
}
