//chockolateman
#include<bits/stdc++.h>
#include "sequence.h"
using namespace std;
int n,a[500005],b[500005],preff[500005];
pair<int,int> temp[500005];
struct Node
{
int maxim,minim,lazy = 0;
} st[2000005];
Node combine(Node left,Node right)
{
Node ret;
ret.maxim = max(left.maxim,right.maxim);
ret.minim = min(left.minim,right.minim);
return ret;
}
void build(int v = 1,int start = 0,int end = n)
{
if(start==end)
{
preff[start] = -start;
st[v].maxim = preff[start];
st[v].minim = preff[start];
return;
}
int mid = (start + end)/2;
build(2*v,start,mid);
build(2*v+1,mid+1,end);
st[v] = combine(st[2*v],st[2*v+1]);
}
void propagate(int v,int start,int end);
void update(int l,int r,int val,int v = 1,int start = 0,int end = n)
{
if(start==l && end==r)
{
st[v].maxim += val;
st[v].minim += val;
st[v].lazy += val;
if(start==end)
preff[start] += val;
return;
}
propagate(v,start,end);
int mid = (start + end)/2;
if(r <= mid)
update(l,r,val,2*v,start,mid);
else if(l > mid)
update(l,r,val,2*v+1,mid+1,end);
else
{
update(l,mid,val,2*v,start,mid);
update(mid+1,r,val,2*v+1,mid+1,end);
}
st[v] = combine(st[2*v],st[2*v+1]);
}
void propagate(int v,int start,int end)
{
if(st[v].lazy)
{
int mid = (start + end)/2;
update(start,mid,st[v].lazy,2*v,start,mid);
update(mid+1,end,st[v].lazy,2*v+1,mid+1,end);
st[v].lazy = 0;
}
}
Node query(int l,int r,int v = 1,int start = 0,int end = n)
{
if(start==l && end==r)
return st[v];
propagate(v,start,end);
int mid = (start + end)/2;
if(r <= mid)
return query(l,r,2*v,start,mid);
else if(l > mid)
return query(l,r,2*v+1,mid+1,end);
else
return combine(query(l,mid,2*v,start,mid),query(mid+1,r,2*v+1,mid+1,end));
}
bool intersect(int i,int j,int x,int y)
{
return i <= y && j >= x;
}
int find_rightest(int l,int r,int v = 1,int start = 0,int end = n)
{
if(start==end)
return start;
propagate(v,start,end);
int mid = (start + end)/2;
if(intersect(l,r,st[2*v+1].minim,st[2*v+1].maxim))
return find_rightest(l,r,2*v+1,mid+1,end);
else
return find_rightest(l,r,2*v,start,mid);
}
int find_leftest(int l,int r,int v = 1,int start = 0,int end = n)
{
if(start==end)
return start;
propagate(v,start,end);
int mid = (start + end)/2;
if(intersect(l,r,st[2*v].minim,st[2*v].maxim))
return find_leftest(l,r,2*v,start,mid);
else
return find_leftest(l,r,2*v+1,mid+1,end);
}
int sequence(int N, std::vector<int> A) {
n = N;
for(int i = 1 ; i <= N ; i++)
{
a[i] = A[i-1];
b[i] = a[i];
temp[i] = {a[i],i};
}
sort(b+1,b+N+1);
int med = (N+1)/2;
int ans = 0;
int cnt = 0;
for(int i = 1 ; i <= N ; i++)
if(b[i]==b[med])
cnt++;
ans = cnt;
cnt = 0;
med = (N+2)/2;
for(int i = 1 ; i <= N ; i++)
if(b[i]==b[med])
cnt++;
ans = max(ans,cnt);
sort(temp+1,temp+N+1);
build();
int r = 1;
int l = 1;
vector<int> poses;
while(l < N)
{
r = l;
while(r < N && temp[r+1].first == temp[l].first)
r++;
int prv = 0;
for(int i = l ; i <= r ; i++)
poses.push_back(temp[i].second);
// //Case 1: First emf being the median
for(int i,k = 0 ; k < (r-l+1) ; k++)
{
i = poses[k];
update(i,N,1);
Node front = query(prv,i-1);
int reach = find_rightest(front.minim - 1,front.maxim + 1);
cnt = upper_bound(poses.begin(),poses.end(),reach) - poses.begin() - k;
ans = max(ans,cnt);
update(i,N,1);
prv = i;
}
int nxt = N+1;
//Case 2: First emf being the median
for(int i,k = (r-l) ; k >= 0 ; k--)
{
i = poses[k];
update(i,N,-1);
Node back = query(i,nxt-1);
int reach = find_leftest(back.minim - 1,back.maxim + 1) + 1;
cnt = k - (lower_bound(poses.begin(),poses.end(),reach) - poses.begin()) + 1;
ans = max(ans,cnt);
update(i,N,-1);
nxt = i;
}
for(auto i : poses)
update(i,N,1);
poses.clear();
l = r+1;
}
return ans;
}
