#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct SegmentTree{
struct node{
T sum;
T Min;
T Max;
T lazy;
bool isUpdated;
node(){
sum = Min = Max = 0;
lazy = 0;
isUpdated = false;
};
node(T x){
sum = Min = Max = x;
lazy = 0;
isUpdated = false;
}
};
vector<node> tree;
node neutral_element;
inline void combine(node &par, node lf, node rg){
par.sum = lf.sum + rg.sum;
par.Min = min(lf.Min, rg.Min);
par.Max = max(lf.Max, rg.Max);
}
int _begin, _end;
inline void init(int n){
_begin = 0;
_end = n - 1;
neutral_element.Min = 2 * n;
neutral_element.Max = -2 * n;
tree.resize(n * 4 + 5);
}
inline void upd(int v, int tl, int tr, T lazy){
tree[v].sum += lazy * (tr - tl + 1);
tree[v].Min += lazy;
tree[v].Max += lazy;
tree[v].isUpdated = true;
tree[v].lazy += lazy;
}
inline void push(int v, int tl, int tr){
if (tl == tr || !tree[v].isUpdated) return;
int tm = (tl + tr) >> 1;
upd(v << 1, tl, tm, tree[v].lazy);
upd(v << 1 | 1, tm + 1, tr, tree[v].lazy);
tree[v].lazy = 0;
tree[v].isUpdated = false;
}
inline void update(int v, int tl, int tr, int l, int r, T val){
push(v, tl, tr);
if (l <= tl && tr <= r){
upd(v, tl, tr, val);
return;
}
if (tl > r || tr < l) return;
int tm = (tl + tr) >> 1;
update(v << 1, tl, tm, l, r, val);
update(v << 1 | 1, tm + 1, tr, l, r, val);
combine(tree[v], tree[v << 1], tree[v << 1 | 1]);
}
inline void update(int l, int r, T val){
update(1, _begin, _end, l, r, val);
}
inline node get(int v, int tl, int tr, int l, int r){
push(v, tl, tr);
if (l <= tl && tr <= r) return tree[v];
if (tl > r || tr < l) return neutral_element;
int tm = (tl + tr) >> 1;
node res;
combine(res, get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
return res;
}
inline node get(int l, int r){
return get(1, _begin, _end, l, r);
}
inline int get(int i){
return get(i, i).sum;
}
};
int sequence(int N, std::vector<int> A) {
A.insert(A.begin(), 0);
vector<vector<int>> pos(N + 1);
for (int i = 1; i <= N; i++){
pos[A[i]].push_back(i);
}
int ans = 1;
int t = 0;
for (int i = 1; i <= N; i++){
if (i == 1 || A[i] == A[i - 1]){
t++;
} else {
t = 1;
}
ans = max(ans, t);
}
SegmentTree<int> st;
st.init(N + 1);
for (int i = 1; i <= N; i++){
st.update(i, N, 1);
}
for (int x = 1; x <= N; x++){
if (pos[x].empty()) continue;
for (int i : pos[x]){ // making 0
st.update(i, N, -1);
}
{
int i = pos[x].front(), j = pos[x].back();
int f = pos[x].size();
int sum = st.get(j) - st.get(i - 1);
if (abs(sum) <= f) ans = max(ans, f);
int l1 = st.get(i) - st.get(0, i).Max;
int r1 = st.get(i) - st.get(0, i).Min;
int l2 = st.get(j, N).Min - st.get(j);
int r2 = st.get(j, N).Max - st.get(j);
l1 = min(l1, 0), l2 = min(l2, 0);
r1 = max(r1, 0), r2 = max(r2, 0);
int need;
if (sum < -f) {
need = -f - sum;
} else {
need = f - sum;
}
if (l1 + l2 <= need && need <= r1 + r2) ans = max(ans, f);
}
for (int i : pos[x]){ // making -1
st.update(i, N, -1);
}
}
return ans;
}
