#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, int paritate)
{
lazy[nod]=0;
if(st==dr)
{
if(st%2==paritate) aint[nod]=0;
else aint[nod]=INF;
return;
}
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, int paritate)
{
lazy[nod]=0;
if(st==dr)
{
if(st%2==paritate) aint[nod]=0;
else aint[nod]=-INF;
return;
}
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_min[2];
SegTreeLazy_max aint_max[2];
bool verif(int le1, int ri1, int le2, int ri2, int cnt0, int N)
{
pair<int,int> x[2],y[2];
for(int i=0;i<2;i++)
{
x[i] = {aint_min[i].qry(1,0,N,le1,ri1), aint_max[i].qry(1,0,N,le1,ri1)};
y[i] = {aint_min[i].qry(1,0,N,le2,ri2), aint_max[i].qry(1,0,N,le2,ri2)};
}
for(int p=0;p<2;p++)
{
for(int q=0;q<2;q++)
{
pair<int,int> a = x[p], b = y[q];
if(a.first > b.first)
swap(a,b);
if(p==q)
{
if(a.second + cnt0 - 1 >= b.first)
return 1;
}
else
{
if(a.second + cnt0 >= b.first)
return 1;
}
}
}
return 0;
}
vector<int> pozs[500005];
int sequence(int N, std::vector<int> A)
{
aint_min[0].build(1,0,N,0);
aint_min[1].build(1,0,N,1);
aint_max[0].build(1,0,N,0);
aint_max[1].build(1,0,N,1);
for(int i=1;i<=N;i++)
{
aint_min[0].upd(1,0,N,i,N,+1);
aint_min[1].upd(1,0,N,i,N,+1);
aint_max[0].upd(1,0,N,i,N,+1);
aint_max[1].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_min[0].upd(1,0,N,x,N,-1);
aint_min[1].upd(1,0,N,x,N,-1);
aint_max[0].upd(1,0,N,x,N,-1);
aint_max[1].upd(1,0,N,x,N,-1);
}
for(int i=0;i<pozs[val].size();i++)
{
for(int j=i;j<pozs[val].size();j++)
{
/*for(int k=0;k<pozs[val].size();k++)
{
int x = pozs[val][k];
if(k<i)
{
aint_min[0].upd(1,0,N,x,pozs[val][i]-1,-1);
aint_min[1].upd(1,0,N,x,pozs[val][i]-1,-1);
aint_max[0].upd(1,0,N,x,pozs[val][i]-1,+1);
aint_max[1].upd(1,0,N,x,pozs[val][i]-1,+1);
}
else if(k>j)
{
aint_min[0].upd(1,0,N,x,N,-1);
aint_min[1].upd(1,0,N,x,N,-1);
aint_max[0].upd(1,0,N,x,N,+1);
aint_max[1].upd(1,0,N,x,N,+1);
}
}*/
if(verif(0,pozs[val][i]-1,pozs[val][j],N,j-i+1,N))
{
mxm = max(mxm, j-i+1);
}
/*for(int k=0;k<pozs[val].size();k++)
{
int x = pozs[val][k];
if(k<i)
{
aint_min[0].upd(1,0,N,x,pozs[val][i]-1,+1);
aint_min[1].upd(1,0,N,x,pozs[val][i]-1,+1);
aint_max[0].upd(1,0,N,x,pozs[val][i]-1,-1);
aint_max[1].upd(1,0,N,x,pozs[val][i]-1,-1);
}
else if(k>j)
{
aint_min[0].upd(1,0,N,x,N,+1);
aint_min[1].upd(1,0,N,x,N,+1);
aint_max[0].upd(1,0,N,x,N,-1);
aint_max[1].upd(1,0,N,x,N,-1);
}
}*/
}
}
for(auto x:pozs[val])
{
aint_min[0].upd(1,0,N,x,N,-1);
aint_min[1].upd(1,0,N,x,N,-1);
aint_max[0].upd(1,0,N,x,N,-1);
aint_max[1].upd(1,0,N,x,N,-1);
}
}
return mxm;
}
