#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
struct Node{
int sum, prf, suf;
Node(){}
Node(int sum, int prf, int suf): sum(sum), prf(prf), suf(suf){}
Node(int x){
sum = x;
prf = suf = max(x, 0);
}
Node operator+(const Node &r)const{
return Node(sum + r.sum, max(prf, sum + r.prf), max(suf + r.sum, r.suf));
}
};
struct segTree{
Node tree[1<<20];
void init(int i, int l, int r, int v){
if(l==r){
tree[i] = Node(v);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, v);
init(i*2+1, m+1, r, v);
tree[i] = tree[i*2] + tree[i*2+1];
}
void update(int i, int l, int r, int x, int v){
if(l==r){
tree[i] = Node(v);
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = tree[i*2] + tree[i*2+1];
}
Node query(int i, int l, int r, int s, int e){
if(r<s || e<l) return Node(0, 0, 0);
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
}
} treeMax, treeMin; /// +0-, -0+
struct minTree{
int tree[1<<21];
void init(int i, int l, int r){
tree[i] = INF;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void update(int i, int l, int r, int x, int v){
if(l==r){
tree[i] = min(tree[i], v);
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
int query(int i, int l, int r, int s, int e){
if(r<s || e<l) return INF;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
int n;
void update_zero(int x){
treeMax.update(1, 1, n, x, 0);
treeMin.update(1, 1, n, x, 0);
}
void update_one(int x){
treeMax.update(1, 1, n, x, -1);
treeMin.update(1, 1, n, x, 1);
}
int arr[500002];
vector<int> occ[500002];
int loc[500002];
int prf1[500002], suf1[500002], btw1[500002];
int prf2[500002], suf2[500002], btw2[500002];
int S1[500002], T1[500002];
int S2[500002], T2[500002];
bool able(int L, int k){
int sum1 = 0, sum2 = 0;
for(int i=1; i<=L-2; i++) sum1 += btw1[i], sum2 += btw2[i];
for(int s=1; s+L-1 <= k; s++){
int e = s+L-1;
sum1 += btw1[e-1] - btw1[s-1], sum2 += btw2[e-1] - btw2[s-1];
int v1 = sum1 + suf1[s] + prf1[e], v2 = sum2 + suf2[s] + prf2[e];
if(v1 >= -L && v2 >= -L) return true;
}
return false;
}
struct Query{
int x, y, idx, type;
Query(){}
Query(int x, int y, int idx, int type): x(x), y(y), idx(idx), type(type){}
bool operator<(const Query &r)const{
if(y!=r.y) return y<r.y;
if(type!=r.type) return type<r.type;
return x<r.x;
}
};
int sequence(int _N, vector<int> A){
n = _N;
for(int i=1; i<=n; i++){
arr[i] = A[i-1];
occ[arr[i]].push_back(i);
}
treeMax.init(1, 1, n, 1), treeMin.init(1, 1, n, -1);
int ans = 1;
for(int v=1; v<=n; v++){
if(occ[v].empty()) continue;
int k = (int)occ[v].size();
for(int i=1; i<=k; i++) loc[i] = occ[v][i-1];
loc[0] = 0, loc[k+1] = n+1;
for(int i=1; i<=k; i++) update_zero(loc[i]);
for(int i=0; i<=k; i++){
int s = loc[i]+1, e = loc[i+1]-1;
Node p1 = treeMax.query(1, 1, n, s, e), p2 = treeMin.query(1, 1, n, s, e);
if(i) prf1[i] = p1.prf, prf2[i] = p2.prf;
if(i<k) suf1[i+1] = p1.suf, suf2[i+1] = p2.suf;
if(i && i<k) btw1[i+1] = btw1[i] + p1.sum + 1, btw2[i+1] = btw2[i] + p2.sum + 1;
}
for(int i=1; i<=k; i++){
S1[i] = btw1[i] - suf1[i], S2[i] = btw2[i] - suf2[i];
T1[i] = btw1[i] + prf1[i] + 1, T2[i] = btw2[i] + prf2[i] + 1;
}
/// (S1, S2) <= (T1, T2)인 점 찾기
vector<int> xVal, yVal;
for(int i=1; i<=k; i++){
xVal.push_back(S1[i]), xVal.push_back(T1[i]);
yVal.push_back(S2[i]), yVal.push_back(T2[i]);
}
sort(xVal.begin(), xVal.end());
sort(yVal.begin(), yVal.end());
xVal.erase(unique(xVal.begin(), xVal.end()), xVal.end());
yVal.erase(unique(yVal.begin(), yVal.end()), yVal.end());
int X = (int)xVal.size();
for(int i=1; i<=k; i++){
S1[i] = lower_bound(xVal.begin(), xVal.end(), S1[i]) - xVal.begin() + 1;
T1[i] = lower_bound(xVal.begin(), xVal.end(), T1[i]) - xVal.begin() + 1;
S2[i] = lower_bound(yVal.begin(), yVal.end(), S2[i]) - yVal.begin() + 1;
T2[i] = lower_bound(yVal.begin(), yVal.end(), T2[i]) - yVal.begin() + 1;
}
vector<Query> vec;
for(int i=1; i<=k; i++){
vec.push_back(Query(S1[i], S2[i], i, 0));
vec.push_back(Query(T1[i], T2[i], i, 1));
}
sort(vec.begin(), vec.end());
tree.init(1, 1, X);
for(Query &p: vec){
if(p.type == 0) tree.update(1, 1, X, p.x, p.idx);
else ans = max(ans, p.idx - tree.query(1, 1, X, 1, p.x) + 1);
}
for(int i=1; i<=k; i++) update_one(loc[i]);
}
return ans;
}
