/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "sequence.h"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
//#define int long long
const int mod = 1e9+9;
using namespace std;
using ll = long long;
const int inf = 1e9+7;
pair<int, int> neutral = {inf, -inf};
pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
return {min(a.first, b.first), max(a.second, b.second)};
}
struct segtree {
vector<pair<int, int>> tree;
vector<int> gos;
int size = 1;
void init(int n) {
//size = 1;
while (size < n)size <<= 1;
tree.assign(2*size-1, {0, 0});
gos.assign(2*size-1, 0);
}
void apply(int l, int r, int v, int x, int lx, int rx) {
if (rx <= l || r <= lx)return;
if (lx >= l && rx <= r) {
gos[x] += v;
tree[x].first += v, tree[x].second += v;
return;
}
int mid = lx + rx >> 1;
apply(l, r, v, 2*x+1, lx, mid), apply(l, r, v, 2*x+2, mid, rx);
tree[x] = tree[2*x+1]+tree[2*x+2];
tree[x].first += gos[x], tree[x].second += gos[x];
}
void apply(int l, int r, int v) {
apply(l, r, v, 0, 0, size);
}
pair<int, int> get(int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx)return neutral;
if (lx >= l && rx <= r)return tree[x];
int mid = lx + rx >> 1;
pair<int, int> s1 = get(l, r, 2*x+1, lx, mid) + get(l, r, 2*x+2, mid, rx);
s1.first += gos[x], s1.second += gos[x];
return s1;
}
pair<int, int> get(int l, int r) {
return get(l, r, 0, 0, size);
}
};
int sequence(int n, vector<int> a) {
vector<pair<int, int>> cnt(n+1, {-1, -1});
for (int i = 0; i < n; ++i) {
int x = a[i];
if (cnt[x].first == -1)cnt[x].first = i;
else cnt[x].second = i;
}
vector<int> adj[n+1];
for (int i = 0; i < n; ++i)
adj[a[i]].push_back(i);
segtree st;
st.init(n+1);
for (int i = 0; i < n; ++i) {
st.apply(i, n, 1);
}
int ans = 1;
for (int i = 1; i <= n; ++i) {
int x = i;
if (sz(adj[x]) <= ans) {
for (auto j: adj[x])
st.apply(j, n, -2);
continue;
}
for (int j:adj[x])
st.apply(j, n, -1);
for (int j = sz(adj[x])-1; j >= 0; --j) {
while (j + ans < sz(adj[x])) {
pair<int, int> l = st.get(0, adj[i][j]);
pair<int, int> r = st.get(adj[i][j+ans], n);
if (r.first >= -ans-1 && r.first <= ans+1) {
ans += 1;
continue;
}
if (r.second >= -ans-1 && r.second <= ans+1) {
ans += 1;
continue;
}
l.first -= (ans+1), l.second += ans+1;
if (max(l.first, r.first) <= min(r.second, l.second))ans++;
else break;
}
}
for (auto j: adj[x])
st.apply(j, n, -1);
}
return ans;
}
