#include "sequence.h"
#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
struct segtree{
struct info{
int mxprf=0;
int mnprf=0;
int mxsuf=0;
int mnsuf=0;
int sum=0;
info(){}
info(int k){
if(k>0)mxprf=mxsuf=sum=0;
else mnprf=mnsuf=sum=k;
}
info(info a,info b){
sum=a.sum+b.sum;
mxprf=max(a.mxprf,b.mxprf+a.sum);
mnprf=min(a.mnprf,b.mnprf+a.sum);
mxsuf=max(b.mxsuf,a.mxsuf+b.sum);
mnsuf=min(b.mnsuf,a.mnsuf+b.sum);
}
} T[1<<20];
void upd(int i,int l,int r,int p,int x){
if(l==r)return void(T[i]=info(x));
if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
else upd(i*2,l,l+r>>1,p,x);
T[i]=info(T[i*2],T[i*2+1]);
}
info qry(int i,int l,int r,int ll,int rr){
if(ll>r||l>rr)return info();
if(ll<=l&&r<=rr) return T[i];
return info(qry(i*2,l,l+r>>1,ll,rr),
qry(i*2+1,l+r+2>>1,r,ll,rr));
}
} TRE;
using namespace __gnu_pbds;
tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>stt;
map<int,int>mp;
int sequence(int N, std::vector<int> A) {
int ans=1;
vector<int>A2=A;
if(N<3000){
for(int i=0;i<N;i++){
mp.clear();
stt.clear();
for(int j=i;j<N;j++){
stt.insert(A[j]);
mp[A[j]]++;
int a=*stt.find_by_order((j-i)/2),b=*stt.find_by_order((j-i+1)/2);
ans=max({ans,mp[a],mp[b]});
}
}
return ans;
}
int dec1=N,dec2=0;
for(int i=1;i<N;i++){
if(A[i]<A[i-1]){
dec1=i;
break;
}
}
for(int i=N;i--;){
if(A[i]>A[i-1]){
dec2=i;
break;
}
}
if(dec1>dec2) {
sort(A2.begin(),A2.end());
int C=A2[N-1>>1];
map<int,int>mp1,mp2;
for(int i=0;i<dec1;i++)
mp1[A[i]]++;
for(int i=dec1;i<N;i++)
mp2[A[i]]++;
for(auto [i,j]:mp1)
ans=max(ans,j);
for(auto [i,j]:mp2)
ans=max(ans,j);
for(int i=0;i<N;i++) if(A[i]>=C)
ans=max(ans,mp1[A[i]]+mp2[A[i]]);
return ans;
}
map<int,int>mp;
for(auto i:A)mp[i];
int CC=0;
for(auto&[i,j]:mp)
j=++CC;
vector<int>v[500100];
for(auto&i:A)
i=mp[i];
for(int i=0;i<N;i++)
v[A[i]].push_back(i+1);
for(int i=1;i<=N;i++)
TRE.upd(1,1,N,i,1);
for(int i=1;i<=CC;i++){
for(auto k:v[i])
TRE.upd(1,1,N,k,0);
if(v[i].size()==2){
int x=TRE.qry(1,1,N,v[i][0],v[i][1]).sum;
if(x>0){
x+=TRE.qry(1,1,N,1,v[i][0]-1).mnsuf;
x+=TRE.qry(1,1,N,v[i][1]+1,N).mnprf;
} else {
x+=TRE.qry(1,1,N,1,v[i][0]-1).mxsuf;
x+=TRE.qry(1,1,N,v[i][1]+1,N).mxprf;
}
if(abs(x)<3) return 2;
}
for(auto k:v[i])
TRE.upd(1,1,N,k,-1);
}
return 1;
}
