#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
struct node{
int s, e, m, mn, mx, lazy;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1; mn = s, mx = e, lazy = 0;
if (s != e){
l = new node(s, m);
r = new node(m + 1, e);
}
}
void update(int x, int y, int v){
if (x == s && y == e){
mn += v; mx += v; lazy += v;
return;
}
else if (y <= m) l->update(x, y, v);
else if (x > m) r->update(x, y, v);
else{
l->update(x, m, v); r->update(m + 1, y, v);
}
mn = min(l->mn, r->mn) + lazy;
mx = max(l->mx, r->mx) + lazy;
}
int mnq(int x, int y){
if (x == s && y == e) return mn;
else if (y <= m) return l->mnq(x, y) + lazy;
else if (x > m) return r->mnq(x, y) + lazy;
else return min(l->mnq(x, m), r->mnq(m + 1, y)) + lazy;
}
int mxq(int x, int y){
if (x == s && y == e) return mx;
else if (y <= m) return l->mxq(x, y) + lazy;
else if (x > m) return r->mxq(x, y) + lazy;
else return max(l->mxq(x, m), r->mxq(m + 1, y)) + lazy;
}
};
vector<int> occ[MAXN];
vector<int> mnlq[MAXN], mxlq[MAXN], mnrq[MAXN], mxrq[MAXN];
int sequence(int N, vector<int> A){
for (int i = 1; i <= N; i++) occ[A[i - 1]].push_back(i);
node *root = new node(0, N);
for (int x = 1; x <= N; x++){
for (int id : occ[x]) root->update(id, N, -1);
int sz = occ[x].size();
for (int i = 0; i < sz; i++){
mnlq[x].push_back(root->mnq(0, occ[x][i] - 1));
mxlq[x].push_back(root->mxq(0, occ[x][i] - 1));
mnrq[x].push_back(root->mnq(occ[x][i], N));
mxrq[x].push_back(root->mxq(occ[x][i], N));
}
for (int id : occ[x]) root->update(id, N, -1);
}
int l = 1, r = N, ans = 1;
while (l <= r){
int m = (l + r) >> 1;
bool ok = 0;
for (int x = 1; x <= N; x++){
int sz = occ[x].size();
for (int l = 0, r = m - 1; r < sz; l++, r++)
if (mnrq[x][r] - mxlq[x][l] <= m && mxrq[x][r] - mnlq[x][l] >= -m)
ok = 1;
}
if (ok){
ans = m; l = m + 1;
}
else r = m - 1;
}
return ans;
}
