#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll sequence(ll n, vector<ll> a) {
if (n <= 2000) {
ll ans = 1;
for (ll i = 0; i < n; i++) {
unordered_map<ll, ll> col;
multiset<ll> now1, now2;
now2.insert(a[i]);
col[a[i]]++;
for (ll j = i + 1; j < n; j++) {
if (a[j] <= *now2.begin()) {
now1.insert(a[j]);
} else {
now2.insert(a[j]);
}
col[a[j]]++;
while (now1.size() < now2.size()) {
now1.insert(*now2.begin());
now2.erase(now2.begin());
}
while (now1.size() > now2.size()) {
now2.insert(*now1.rbegin());
now1.erase(now1.find(*now1.rbegin()));
}
if (ans < col[*now2.begin()]) {
ans = col[*now2.begin()];
}
if (now1.size() == now2.size()) {
if (ans < col[*now1.rbegin()]) {
ans = col[*now1.rbegin()];
}
}
}
}
return ans;
} else {
ll ans = 1;
ll lst = -1, c = 0;
for (auto i : a) {
if (i == lst) {
c++;
} else {
if (ans < c) {
ans = c;
}
lst = i;
c = 1;
}
}
if (ans < c) {
ans = c;
}
map<ll, ll> col, fir, last;
for (ll i = 0; i < n; i++) {
col[a[i]]++;
last[a[i]] = i;
}
for (ll i = n - 1; i >= 0; i--) {
fir[a[i]] = i;
}
for (auto i : a) {
ll cb = last[i] - fir[i] + 1 - col[i];
ll cm = n - cb - col[i];
if (cm + col[i] >= cb) {
if (ans < col[i]) {
ans = col[i];
}
}
}
return ans;
}
}
