#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const int N=5e5+5;
int n,a[N],lo,hi;
vector<int>pos[N];
struct segtree{
int mx[4*N],mn[4*N],lazy[4*N];
void add(int v,int x){
mx[v]+=x;
mn[v]+=x;
lazy[v]+=x;
}
void push(int v){
if(lazy[v]==0) return;
add(v<<1,lazy[v]);
add(v<<1|1,lazy[v]);
lazy[v]=0;
}
void merge(int v){
mx[v]=max(mx[v<<1],mx[v<<1|1]);
mn[v]=min(mn[v<<1],mn[v<<1|1]);
}
void update(int v,int l,int r,int L,int R,int val){
if(R<L||r<L||R<l) return;
if(L<=l&&r<=R){
add(v,val);
return;
}
push(v);
int m=(l+r)>>1;
update(v<<1,l,m,L,R,val);
update(v<<1|1,m+1,r,L,R,val);
merge(v);
}
void query(int v,int l,int r,int L,int R){
if(R<L||r<L||R<l) return;
if(L<=l&&r<=R){
lo=min(lo,mn[v]);
hi=max(hi,mx[v]);
return;
}
push(v);
int m=(l+r)>>1;
query(v<<1,l,m,L,R);
query(v<<1|1,m+1,r,L,R);
}
};
int sequence(int N,vector<int>A){
n=N;
for(int i=1;i<=n;i++){
a[i]=A[i-1];
pos[a[i]].pb(i);
}
segtree more,less;
for(int i=1;i<=n;i++){
more.update(1,1,n,i,n,-1);
}
for(int i=1;i<=n;i++){
less.update(1,1,n,i,n,-1);
}
int ans=0;
for(int x=1;x<=n;x++){
for(int p:pos[x]){
more.update(1,1,n,p,n,+2);
}
int j=0;
for(int i=0;i<pos[x].size();i++){
while(j<i){
int v1,v2;
hi=-1e9,more.query(1,1,n,pos[x][i],n);
v1=hi;
lo=0,more.query(1,1,n,1,pos[x][j]-1);
v1-=lo;
lo=1e9,less.query(1,1,n,pos[x][i],n);
v2=lo;
hi=0,less.query(1,1,n,1,pos[x][j]-1);
v2-=hi;
if(1ll*v1*v2>0) j++;
else break;
}
ans=max(ans,i-j+1);
}
for(int p:pos[x]){
less.update(1,1,n,p,n,+2);
}
}
return ans;
}
