// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int N,m,q;
struct Node {
int mn, mx, tag;
Node() : mn(INF), mx(-INF), tag(0) {};
Node(int v) : mn(v), mx(v), tag(0) {};
Node merge(Node &oth) {
Node ret;
ret.mx = max(oth.mx, mx);
ret.mn = min(oth.mn, mn);
return ret;
}
void add(int x) {
mn += x;
mx += x;
tag += x;
}
};
struct SegTree {
vector<Node> data;
int sz;
SegTree() : sz(0) {}
void reset(int s) {
sz = s;
data.assign(4*(sz + 3), Node());
}
void push(int v) {
data[v<<1].add(data[v].tag);
data[v<<1^1].add(data[v].tag);
data[v].tag = 0;
}
void build(int tl, int tr, int v, vector<int> &vec) {
if(tl == tr) {
data[v] = Node(vec[tl]);
return;
}
int tm = (tl + tr) >> 1;
build(tl, tm, v<<1, vec);
build(tm + 1, tr, v<<1^1, vec);
data[v] = data[v<<1].merge(data[v<<1^1]);
}
int getMin(int tl, int tr, int v, int l, int r) {
if(tl >= l && tr <= r) {
return data[v].mn;
}
if(tl > r || tr < l) return INF;
int tm = (tl + tr) >> 1;
push(v);
return min(getMin(tl, tm, v<<1, l, r), getMin(tm + 1, tr, v<<1^1, l, r));
}
int getMin(int l, int r) {
l = max(0, l); r = min(sz, r);
if(l > r) {
// cout<<"MIN:"<<l<<" "<<r<<" val:"<<0<<"\n";
return 0;
}
// cout<<"MIN:"<<l<<" "<<r<<" val:"<<getMin(0, sz, 1, l, r)<<"\n";
return getMin(0, sz, 1, l, r);
}
int getMax(int tl, int tr, int v, int l, int r) {
if(tl >= l && tr <= r) {
return data[v].mx;
}
if(tl > r || tr < l) return -INF;
int tm = (tl + tr) >> 1;
push(v);
return max(getMax(tl, tm, v<<1, l, r), getMax(tm + 1, tr, v<<1^1, l, r));
}
int getMax(int l, int r) {
l = max(0, l); r = min(sz, r);
if(l > r) {
// cout<<"MAX:"<<l<<" "<<r<<" val:"<<0<<"\n";
return 0;
}
// cout<<"MAX:"<<l<<" "<<r<<" val:"<<getMax(0, sz, 1, l, r)<<"\n";
return getMax(0, sz, 1, l, r);
}
void update(int tl, int tr, int v, int l, int r, int val) {
if(tl >= l && tr <= r) {
data[v].add(val);
return;
}
if(tl > r || tr < l) {
return;
}
int tm = (tl + tr) >> 1;
push(v);
update(tl, tm, v<<1, l, r, val);
update(tm + 1, tr, v<<1^1, l, r, val);
data[v] = data[v<<1].merge(data[v<<1^1]);
}
void update(int l, int r, int val) {
l = max(0, l); r = min(sz, r);
if(l > r) return;
update(0, sz, 1, l, r, val);
}
};
SegTree st, st2;
vector<vector<int> > occ;
vector<int> pr;
int sequence(int n, vector<int> a) {
N = n;
st.reset(n - 1); st2.reset(n - 1);
occ.assign(n + 1, vector<int>());
pr.assign(n, 0);
for(int i = 0; i<n; i++) {
occ[a[i]].pb(i);
}
pr[0] = 1;
for(int i = 1; i<n; i++) pr[i] = pr[i - 1] + 1;
st.build(0, n - 1, 1, pr);
st2.build(0, n - 1, 1, pr);
int ans = 1;
for(int v = 1; v<=n; v++) {
for(auto c : occ[v]) {
st2.update(c, n - 1, -2);
}
int l = 0;
for(int r = 0; r<occ[v].size(); r++) {
while(l <= r) {
int fir = occ[v][l], sec = occ[v][r];
int v1 = st.getMax(sec, n - 1) - min(0, st.getMin(0, fir - 1));
int v2 = st2.getMin(sec, n - 1) - max(0, st2.getMax(0, fir - 1));
if(1ll * v1 * v2 <= 0ll) {
ans = max(ans , r - l + 1);
break;
}
l++;
}
}
// cout<<"i:"<<i<<" mn: "<<mn<<" mx:"<<mx<<"\n";
for(auto c : occ[v]) {
st.update(c, n - 1, -2);
}
}
return ans;
}
