#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
struct node{
int s, e, m, mn, mx, lazy;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1; mn = s, mx = e, lazy = 0;
if (s != e){
l = new node(s, m);
r = new node(m + 1, e);
}
}
void update(int x, int y, int v){
if (x == s && y == e){
mn += v; mx += v; lazy += v;
return;
}
else if (y <= m) l->update(x, y, v);
else if (x > m) r->update(x, y, v);
else{
l->update(x, m, v); r->update(m + 1, y, v);
}
mn = min(l->mn, r->mn) + lazy;
mx = max(l->mx, r->mx) + lazy;
}
int mnq(int x, int y){
if (x == s && y == e) return mn;
else if (y <= m) return l->mnq(x, y) + lazy;
else if (x > m) return r->mnq(x, y) + lazy;
else return min(l->mnq(x, m), r->mnq(m + 1, y)) + lazy;
}
int mxq(int x, int y){
if (x == s && y == e) return mx;
else if (y <= m) return l->mxq(x, y) + lazy;
else if (x > m) return r->mxq(x, y) + lazy;
else return max(l->mxq(x, m), r->mxq(m + 1, y)) + lazy;
}
};
vector<int> occ[MAXN];
int sequence(int N, vector<int> A){
for (int i = 1; i <= N; i++) occ[A[i - 1]].push_back(i);
node *root = new node(0, N);
int ans = 0;
for (int x = 1; x <= N; x++){
for (int id : occ[x]) root->update(id, N, -1);
int sz = occ[x].size();
for (int l = 0, r = 0; l < sz; l++)
for (; r < sz; r++){
int mnl = root->mnq(0, occ[x][l] - 1), mxl = root->mxq(0, occ[x][l] - 1);
int mnr = root->mnq(occ[x][r], N), mxr = root->mxq(occ[x][r], N);
int len = r - l + 1;
if (mnr - mxl <= len && mxr - mnl >= -len) ans = max(ans, len);
else break;
}
for (int id : occ[x]) root->update(id, N, -1);
}
return ans;
}
