#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)
const int N = 5e5 + 5;
const int inf = 2e9;
int n;
vector <int> pos[N];
struct t{
int m1 = 0, M1 = 0, m2 = 0, M2 = 0;
}zero = {inf, -inf, inf, -inf};
struct ST{
t st[4*N];
ii lazy[4*N], Zero;
t merge(t a, t b){
return {min(a.m1, b.m1), max(a.M1, b.M1), min(a.m2, b.m2), max(a.M2, b.M2)};
}
void UPD(int id, ii a){
st[id].m1 += a.first, st[id].M1 += a.first, st[id].m2 += a.second, st[id].M2 += a.second;
lazy[id].first += a.first;
lazy[id].second += a.second;
}
void down(int id){
if(lazy[id].first != 0 or lazy[id].second != 0){
UPD(id<<1, lazy[id]), UPD(id<<1|1, lazy[id]);
lazy[id] = Zero;
}
}
void Upd(int id, int l, int r, int x, int y, ii val){
if(r < x or y < l) return;
if(x <= l and r <= y){
UPD(id, val);
return;
}
down(id);
int m = (l+r)>>1;
Upd(id<<1, l, m, x, y, val), Upd(id<<1|1, m+1, r, x, y, val);
st[id] = merge(st[id<<1], st[id<<1|1]);
}
t query(int id, int l, int r, int x, int y){
if(r < x or y < l) return zero;
if(x <= l and r <= y) return st[id];
down(id);
int m = (l+r)>>1;
return merge(query(id<<1, l, m, x, y), query(id<<1|1, m+1, r, x, y));
}
ii val(int pos){
if(pos == 0) return Zero;
t C = query(1, 1, n, pos, pos);
return {C.m1, C.m2};
}
void upd(int node, ii val){
Upd(1, 1, n, node, n, val);
}
}st;
int sign(int x){
if(x == 0) return x;
return x / abs(x);
}
bool check(int x, int y){
ii R1 = st.val(x-1), R2 = st.val(y);
int VL1 = R1.first, VR1 = R2.first, sum1 = VR1 - VL1;
int VL2 = R1.second, VR2 = R2.second, sum2 = VR2 - VL2;
int maL = 0, maR = 0;
int miL = 0, miR = 0;
if(x != 1){
t C = st.query(1, 1, n, 1, x-1);
maL = max(0, max(VL1, VL1 - C.m1));
miL = min(0, min(VL2, VL2 - C.M2));
}
if(y != n){
t C = st.query(1, 1, n, y+1, n);
maR = max(0, C.M1 - VR1);
miR = min(0, C.m2 - VR2);
}
return sign(sum1 + maL + maR) * sign (sum2 + miL + miR) <= 0;
}
int sequence(int Ni, vector<int> A) {
n = Ni;
f(i,0,n){
pos[A[i]].push_back(i+1);
}
f(i,1,n+1){
st.upd(i, {1, 1});
}
int ans = 1;
f(i,1,n+1){
int len = pos[i].size();
for(int x: pos[i]){
st.upd(x, {0, -2});
}
int r = -1;
f(j,0,len){
r = max(r, j);
while(r < len and check(pos[i][j], pos[i][r])) r++;
r--;
ans = max(ans, r - j + 1);
}
for(int x: pos[i]){
st.upd(x, {-2, 0});
}
}
return ans;
}
