#include "sequence.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
using namespace std;
const int INF = 1e9 + 7;
const int N = 5e5 + 5;
int sgmax[N << 2];
int sgmin[N << 2];
int lz[N << 2];
int a[N];
vector<int> pos[N];
void push(int nd, int s, int e) {
if (lz[nd]) {
sgmin[nd] += lz[nd];
sgmax[nd] += lz[nd];
if (s != e) {
lz[nd << 1] += lz[nd];
lz[nd << 1 | 1] += lz[nd];
}
lz[nd] = 0;
}
}
void build(int nd, int s, int e) {
if (s == e) {
sgmax[nd] = sgmin[nd] = s;
return;
}
int mid = s + e >> 1;
build(nd << 1, s, mid);
build(nd << 1 | 1, mid + 1, e);
sgmax[nd] = max(sgmax[nd << 1], sgmax[nd << 1 | 1]);
sgmin[nd] = min(sgmin[nd << 1], sgmin[nd << 1 | 1]);
}
void upd(int nd, int s, int e, int l, int r, int val) {
push (nd, s, e);
if (s > r or l > e) return;
if (l <= s and e <= r) {
lz[nd] += val;
push (nd, s, e);
return;
}
int mid = s + e >> 1;
upd(nd << 1, s, mid, l, r, val);
upd(nd << 1 | 1, mid + 1, e, l, r, val);
sgmax[nd] = max(sgmax[nd << 1], sgmax[nd << 1 | 1]);
sgmin[nd] = min(sgmin[nd << 1], sgmin[nd << 1 | 1]);
}
int qrymin(int nd, int s, int e, int l, int r) {
push (nd, s, e);
if (s > r or l > e) return INF;
if (l <= s and e <= r) {
return sgmin[nd];
}
int mid = s + e >> 1;
int L = qrymin(nd << 1, s, mid, l, r);
int R = qrymin(nd << 1 | 1, mid + 1, e, l, r);
return min(L, R);
}
int qrymax(int nd, int s, int e, int l, int r) {
push (nd, s, e);
if (s > r or l > e) return -INF;
if (l <= s and e <= r) {
return sgmax[nd];
}
int mid = s + e >> 1;
int L = qrymax(nd << 1, s, mid, l, r);
int R = qrymax(nd << 1 | 1, mid + 1, e, l, r);
return max(L, R);
}
int sequence (int n, vector<int> A) {
for (int i = 1;i<=n;++i) pos[i].clear();
build(1, 0, n);
for (int i = 1;i<=n;++i) pos[A[i - 1]].pb(i);
int ans = 1;
for (int x = 1;x<=n;++x) {
if (pos[x].empty()) continue;
int m = ls(pos[x]);
vector<int> maxj1(m), maxj2(m);
int j = 0;
for (int i = 0;i<m;++i) {
j = max(j, i);
while (j < m) {
int x1 = pos[x][i];
int x2 = pos[x][j];
int v1 = qrymax(1, 0, n, x2, n) - qrymin(1, 0, n, 0, x1 - 1);
if (v1 >= 0) j += 1;
else break;
}
maxj1[i] = j - 1;
}
for (auto p : pos[x]) upd(1, 0, n, p, n, -2);
j = 0;
for (int i = 0;i<m;++i) {
j = max(j, i);
while (j < m) {
int x1 = pos[x][i];
int x2 = pos[x][j];
int v2 = qrymin(1, 0, n, x2, n) - qrymax(1, 0, n, 0, x1 - 1);
if (v2 <= 0) j += 1;
else break;
}
maxj2[i] = j - 1;
}
for (int i = 0;i<m;++i) {
ans = max(ans, min(maxj1[i], maxj2[i]) - i + 1);
}
}
return ans;
}
/*
7
1 2 3 1 2 3
9
1 1 2 3 4 3 2 1 1
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/
