#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct SegTreeLazy_min
{
int aint[1100000],lazy[1100000];
void build(int nod, int st, int dr)
{
lazy[nod]=0;
if(st==dr)
{
aint[nod]=0;
return;
}
int mij=(st+dr)/2;
build(nod*2,st,mij);
aint[nod] = min(aint[nod*2], aint[nod*2+1]);
}
void propagate(int nod)
{
lazy[nod*2]+=lazy[nod];
lazy[nod*2+1]+=lazy[nod];
aint[nod*2]+=lazy[nod];
aint[nod*2+1]+=lazy[nod];
lazy[nod]=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
lazy[nod]+=newv;
aint[nod]+=newv;
return;
}
propagate(nod);
int mij=(st+dr)/2;
upd(nod*2,st,mij,le,min(mij,ri),newv);
upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
aint[nod] = min(aint[nod*2], aint[nod*2+1]);
}
int qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return INF;
if(le==st && dr==ri)
return aint[nod];
propagate(nod);
int mij=(st+dr)/2;
return min(qry(nod*2,st,mij,le,min(mij,ri)),
qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
};
struct SegTreeLazy_max
{
int aint[1100000],lazy[1100000];
void build(int nod, int st, int dr)
{
lazy[nod]=0;
if(st==dr)
{
aint[nod]=0;
return;
}
int mij=(st+dr)/2;
build(nod*2,st,mij);
aint[nod] = max(aint[nod*2], aint[nod*2+1]);
}
void propagate(int nod)
{
lazy[nod*2]+=lazy[nod];
lazy[nod*2+1]+=lazy[nod];
aint[nod*2]+=lazy[nod];
aint[nod*2+1]+=lazy[nod];
lazy[nod]=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
lazy[nod]+=newv;
aint[nod]+=newv;
return;
}
propagate(nod);
int mij=(st+dr)/2;
upd(nod*2,st,mij,le,min(mij,ri),newv);
upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
aint[nod] = max(aint[nod*2], aint[nod*2+1]);
}
int qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return -INF;
if(le==st && dr==ri)
return aint[nod];
propagate(nod);
int mij=(st+dr)/2;
return max(qry(nod*2,st,mij,le,min(mij,ri)),
qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
};
SegTreeLazy_min aint_plus_min,aint_minus_min;
SegTreeLazy_max aint_plus_max,aint_minus_max;
bool verif(int le, int ri, int cnt0, int N)
{
if(aint_minus_min.qry(1,0,N,ri,N) > aint_minus_max.qry(1,0,N,0,le-1))
return 0;
if(aint_plus_min.qry(1,0,N,0,le-1) > aint_plus_max.qry(1,0,N,ri,N))
return 0;
return 1;
}
vector<int> pozs[500005];
int sequence(int N, std::vector<int> A)
{
for(int i=1;i<=N;i++)
{
aint_plus_min.upd(1,0,N,i,N,+1);
aint_plus_max.upd(1,0,N,i,N,+1);
aint_minus_min.upd(1,0,N,i,N,+1);
aint_minus_max.upd(1,0,N,i,N,+1);
pozs[A[i-1]].push_back(i);
}
int mxm=1;
for(int val=1;val<=N;val++)
{
for(auto x:pozs[val])
{
aint_plus_min.upd(1,0,N,x,N,-1);
aint_plus_max.upd(1,0,N,x,N,-1);
aint_minus_min.upd(1,0,N,x,N,-1);
aint_minus_max.upd(1,0,N,x,N,-1);
aint_plus_min.upd(1,0,N,x,N,+1);
aint_plus_max.upd(1,0,N,x,N,+1);
aint_minus_min.upd(1,0,N,x,N,-1);
aint_minus_max.upd(1,0,N,x,N,-1);
}
for(int i=0;i<pozs[val].size();i++)
{
for(int j=i+mxm;j<pozs[val].size();j++)
{
if(verif(pozs[val][i],pozs[val][j],j-i+1,N))
{
mxm = max(mxm, j-i+1);
}
else
break;
}
}
for(auto x:pozs[val])
{
aint_plus_min.upd(1,0,N,x,N,-1);
aint_plus_max.upd(1,0,N,x,N,-1);
aint_minus_min.upd(1,0,N,x,N,+1);
aint_minus_max.upd(1,0,N,x,N,+1);
aint_plus_min.upd(1,0,N,x,N,-1);
aint_plus_max.upd(1,0,N,x,N,-1);
aint_minus_min.upd(1,0,N,x,N,-1);
aint_minus_max.upd(1,0,N,x,N,-1);
}
}
return mxm;
}
