#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
int sequence(int N, std::vector<int> a) {
vector<vector<int>> occ(N + 1);
vector<int> A(N + 1);
for(int i = 0;i < N;i ++){
A[i + 1] = a[i];
}
for(int i = 1;i <= N;i ++){
occ[A[i]].emplace_back(i);
}
//segtree 1
//a[i] > x -> 1
//a[i] = x -> 1
//a[i] < x -> -1
//segtree 2
//a[i] > x -> 1
//a[i] = x -> -1
//a[i] < x -> -1
vector<vector<int>> stw(N + 1 , vector<int>(2 , +1));
vector<vector<int>> lz(4 * N , vector<int>(2));
vector<vector<int>> st(4 * N , vector<int>(2));
auto join = [&](int x , int y , int w){
if(w == 0){
return max(x , y);
}
return min(x , y);
};
function<void(int , int , int)> build = [&](int u , int l , int r){
if(l == r){
for(int w = 0;w < 2;w ++){
st[u][w] = r - 1;
}
return;
}
int m = (l + r) / 2;
build(u * 2 , l , m);
build(u * 2 + 1 , m + 1 , r);
for(int w = 0;w < 2;w ++){
st[u][w] = join(st[u * 2][w] , st[u * 2 + 1][w] , w);
}
};
build(1 , 1 , N + 1);
auto push = [&](int u , int w){
st[u * 2][w] += lz[u][w];
st[u * 2 + 1][w] += lz[u][w];
lz[u * 2][w] += lz[u][w];
lz[u * 2 + 1][w] += lz[u][w];
lz[u][w] = 0;
};
function<void(int , int , int , int , int , int , int)> update = [&](int w , int u , int l , int r , int L , int R , int x){
if(l > r || r < L || l > R){
return;
}
if(L <= l && r <= R){
st[u][w] += x;
lz[u][w] += x;
return;
}
push(u , w);
int m = (l + r) / 2;
update(w , u * 2 , l , m , L , R , x);
update(w , u * 2 + 1 , m + 1 , r , L , R , x);
st[u][w] = join(st[u * 2][w] , st[u * 2 + 1][w] , w);
};
function<int(int , int , int , int , int , int)> query = [&](int w , int u , int l , int r , int L , int R){
if(l > r || r < L || l > R){
return (int)(w ? 1E9 : -1E9);
}
if(L <= l && r <= R){
return st[u][w];
}
push(u , w);
int m = (l + r) / 2;
return join(query(w , u * 2 , l , m , L , R) , query(w , u * 2 + 1 , m + 1 , r , L , R) , w);
};
auto set = [&](int w , int pos , int val){
update(w , 1 , 1 , N + 1 , pos + 1 , N + 1 , val - stw[pos][w]);
stw[pos][w] = val;
};
auto check = [&](int l , int r , int v){
int lmax = query(0 , 1 , 1 , N + 1 , 1 , l);
int rmax = query(0 , 1 , 1 , N + 1 , r + 1 , N + 1);
int lmin = query(1 , 1 , 1 , N + 1 , 1 , l);
int rmin = query(1 , 1 , 1 , N + 1 , r + 1 , N + 1);
// cout << "checking " << l << " " << r << '\n';
// cout << "max is " << v << '\n';
int val_min = rmin - lmax;
int val_max = rmax - lmin;
// cout << val_min << " and " << val_max << '\n';
return !(val_max < -v || val_min > v);
};
int ans = 0;
for(int i = 1;i <= N;i ++){
for(int x : occ[i]){
set(0 , x , 1);
set(1 , x , -1);
}
int r = -1;
for(int j = 0;j < (int)occ[i].size();j ++){
while(r + 1 < (int)occ[i].size()){
++r;
set(0 , occ[i][r] , 0);
set(1 , occ[i][r] , 0);
if(!check(occ[i][j] , occ[i][r] , r - j + 1)){
set(0 , occ[i][r] , 1);
set(1 , occ[i][r] , -1);
--r;
break;
}
// cout << "r moved" << '\n';
// cout << '\n';
// cout << '\n';
}
ans = max(ans , r - j + 1);
set(0 , occ[i][j] , 1);
set(0 , occ[i][j] , -1);
}
for(int x : occ[i]){
set(0 , x , -1);
set(1 , x , -1);
}
}
return ans;
}
