#include "bits/stdc++.h"
#include "sequence.h"
#include <cassert>
using namespace std;
const int inf = 1e9;
const int N = 5e5+5;
int trmin[4*N];
int trmax[4*N];
int lz[4*N];
void gur(int nd,int st,int en){
lz[nd] = 0;
if (st == en){
trmin[nd] = st;
trmax[nd] = st;
return;
}
int m = (st+en)>>1;
gur(nd<<1,st,m);
gur(nd<<1|1,m+1,en);
trmin[nd] = min(trmin[nd<<1],trmin[nd<<1|1]);
trmax[nd] = max(trmax[nd<<1],trmax[nd<<1|1]);
}
void push(int nd,int st,int en){
if (lz[nd]){
trmin[nd] += lz[nd];
trmax[nd] += lz[nd];
if (st ^ en){
lz[nd<<1] += lz[nd];
lz[nd<<1|1] += lz[nd];
}
lz[nd] = 0;
}
}
void upd(int nd,int st,int en,int l,int r,int x){
push(nd,st,en);
if (st > en || st > r || en < l)
return;
if (st >= l && en <= r){
lz[nd] += x;
push(nd,st,en);
return;
}
int m = (st+en)>>1;
upd(nd<<1,st,m,l,r,x);
upd(nd<<1|1,m+1,en,l,r,x);
trmin[nd] = min(trmin[nd<<1],trmin[nd<<1|1]);
trmax[nd] = max(trmax[nd<<1|1],trmax[nd<<1]);
}
int querymin(int nd,int st,int en,int l,int r){
if (st > en || st > r || en < l)
return inf;
push(nd,st,en);
if (st >= l && en <= r)
return trmin[nd];
int m = (st + en)>>1;
return min(querymin(nd<<1,st,m,l,r),querymin(nd<<1|1,m+1,en,l,r));
}
int querymax(int nd,int st,int en,int l,int r){
if (st > en || st > r || en < l)
return -inf;
push(nd,st,en);
if (st >= l && en <= r)
return trmax[nd];
int m = (st+en)>>1;
return max(querymax(nd<<1,st,m,l,r),querymax(nd<<1|1,m+1,en,l,r));
}
int sequence(int n,vector <int> a){
vector <vector <int>> in(n+1);
for (int i = 0;i < n;i++){
in[a[i]].push_back(i);
}
gur(1,0,n);
int p = 1;
for (int x = 1;x <= n;x++){
int m = in[x].size();
if (!m)
continue;
vector <int> l(m),r(m);
for (int i = 0;i < m;i++){
l[i] = querymin(1,0,n,0,in[x][i]);
r[i] = querymax(1,0,n,in[x][i]+1,n);
}
for (int i = 0;i < m;i++){
upd(1,0,n,in[x][i]+1,n,-2);
}
vector <int> l1(m),r1(m);
for (int i = 0;i < m;i++){
l1[i] = querymax(1,0,n,0,in[x][i]);
r1[i] = querymin(1,0,n,in[x][i]+1,n);
}
for (int i = 0;i < m;i++){
while (i+p < m){
int j = i+p;
if (r[j]-l[i] >= 0 && r1[j]-l1[i] <= 0)
p++;
else break;
}
}
}
return p;
}
// int main() {
// freopen("file.in","r",stdin);
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<int> A(N);
// for (int i = 0; i < N; ++i) {
// assert(1 == scanf("%d", &A[i]));
// }
// int result = sequence(N, A);
// printf("%d\n", result);
// return 0;
// }
