#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
#include "sequence.h"
using ordered_set = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;
struct MST {
int n;
vector<vector<int>> t;
MST(vector<int> a) : n(a.size()), t(n << 2) {
build(1, 1, n, a);
}
void build(int v, int l, int r, vector<int> &a) {
if(l == r) {
t[v] = {a[l - 1]};
return;
}
int m = (l + r) >> 1;
build(v << 1, l, m, a);
build(v << 1 | 1, m + 1, r, a);
merge(all(t[v << 1]), all(t[v << 1 | 1]), back_inserter(t[v]));
}
int get(int v, int l, int r, int ll, int rr, int x) {
if(l > rr || r < ll) return 0;
if(l >= ll && r <= rr) {
return lower_bound(all(t[v]), x) - t[v].begin();
}
int m = (l + r) >> 1;
return get(v << 1, l, m, ll, rr, x) + get(v << 1 | 1, m + 1, r, ll, rr, x);
}
int get(int l, int r, int x) {
return get(1, 1, n, l, r, x);
}
};
int sequence(int n, std::vector<int> a) {
for(auto &x : a) x--;
vector<vector<int>> idx(n);
for(int i = 0; i < n; i++) {
idx[a[i]].pb(i);
}
MST t(a);
auto is_med = [&](int l, int r, int x, int freq) {
int got = t.get(l + 1, r + 1, x);
int l1 = l + got, r1 = l + got + freq - 1;
int l2 = (l + r) >> 1, r2 = (l + r + 1) >> 1;
// cout << nl;
// cout << l << ' ' << r << nl;
// cout << l1 << ' ' << r1 << nl;
// cout << l2 << ' ' << r2 << nl;
// cout << nl;
return max(l1, l2) <= min(r1, r2);
};
// cout << is_med(0, 8, 0, 4) << nl;
auto check = [&](int x) {
for(int i = 0; i < n; i++) {
if((int)idx[i].size() < x) continue;
for(int j = 0; j < (int)idx[i].size(); j++) {
for(int k = j; k < (int)idx[i].size(); k++) {
if(k - j + 1 < x) continue;
if(is_med(idx[i][j], idx[i][k], i, k - j + 1)) {
// cout << "Yes: " << x << ' ' << i + 1 << ' ' << j << nl;
return true;
}
}
}
}
return false;
};
int l = 0, r = 1e9;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
assert(l >= 1 && l <= n);
return l;
}
