#include "sequence.h"
#include "bits/stdc++.h"
using namespace std;
template<typename T> struct SegTree {
vector<T> tree;
int size;
T neutral_element = 1e9; // sum - 0, mx - (-INF), mn - INF
inline T merge(T a, T b) {
return min(a, b);
}
void init(int n) {
size = 1;
while (size <= n) size *= 2;
tree.assign(2 * size, neutral_element);
}
void build(vector<T> &a) {
size = 1;
while (size < a.size()) size *= 2;
tree.assign(2 * size, neutral_element);
for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
for (int i = size - 1; i > 0; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
}
void upd(int p, T value) { // upd value at position p
p += size;
tree[p] = merge(value, tree[p]);
for (; p > 1; p >>= 1) tree[p >> 1] = merge(tree[p], tree[p ^ 1]);
}
T get(int l, int r) { // sum on interval [l, r]
if (l > r) return neutral_element;
T res = neutral_element;
for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = merge(res, tree[l++]);
if (r & 1) res = merge(res, tree[--r]);
}
return res;
}
};
int sequence(int n, vector<int> a) {
auto b = a;
sort(b.begin(), b.end());
int ans = count(b.begin(), b.end(), b[(n - 1) / 2]);
ans = max(ans, (int) count(b.begin(), b.end(), b[n / 2]));
vector pref(4, vector(n, 0));
for (int i = 0; i < n; i++) pref[a[i]][i]++;
for (int v = 1; v <= 3; v++) for (int i = 1; i < n; i++) pref[v][i] += pref[v][i - 1];
for (int v = 1; v <= 3; v++) {
if (v == 2) continue;
vector<int> val(n);
for (int i = 0; i < n; i++) val[i] = a[i] == v ? 1 : -1;
SegTree<int> sg; sg.init(2 * n + 1);
sg.upd(n, -1);
int sum = 0;
for (int i = 0; i < n; i++) {
sum += val[i];
int pos = sg.get(0, sum + n);
sg.upd(sum + n, i);
if (pos < n) {
ans = max(ans, pref[v][i] - (pos > 0 ? pref[v][pos - 1] : 0));
}
}
}
return ans;
}
