#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int oar[500005];
pair<pair<int,int>,int>sar[500005];
pair<pair<int,int>,int>tar[500005];
int ans;
void slv(int l,int r){
if(l==r){return;}
if(l>r){return;}
int mi=(l+r)/2;
slv(l,mi);slv(mi+1,r);
int lmn=1e9;
int lit=l;int rit=mi+1;
for(int i=l;i<=r;i++){
if( ((rit==r+1)||(lit<=mi&&sar[lit].first.second<=sar[rit].first.second))){
tar[i]=sar[lit];
lmn=min(lmn,sar[lit].second);
lit++;
}else{
tar[i]=sar[rit];
ans=max(ans,sar[rit].second-lmn);
rit++;
}
}
for(int i=l;i<=r;i++){
sar[i]=tar[i];
}
}
int fslv(){
ans=1;
for(int v=1;v<=3;v++){
for(int i=0;i<=n;i++){
sar[i]=sar[max(i-1,0)];
if(oar[i]<v){
sar[i].first.first--;
}else{
sar[i].first.first++;
}
if(oar[i]>v){
sar[i].first.second--;
}else{
sar[i].first.second++;
}
if(oar[i]==v){
sar[i].second++;
}
}
sort(sar+0,sar+n+1);
slv(0,n);
}
return ans;
}
int sequence(int N, std::vector<int> A) {
n=N;
for(int i=0;i<n;i++){
oar[i+1]=A[i];
}
return fslv();
return 0;
}
/*
signed main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>oar[i];
}
ans=1;
for(int v=1;v<=n;v++){
for(int i=0;i<=n;i++){
sar[i]=sar[max(i-1,0)];
if(oar[i]<v){
sar[i].first.first--;
}else{
sar[i].first.first++;
}
if(oar[i]>v){
sar[i].first.second--;
}else{
sar[i].first.second++;
}
if(oar[i]==v){
sar[i].second++;
}
}
sort(sar+0,sar+n+1);
slv(0,n);
}
cout<<ans<<endl;
return 0;
}
*/
