#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
int sequence(int n, std::vector<int> a) {
int cnt1 = count(all(a), 1);
int cnt2 = count(all(a), 3);
if(cnt1 >= (n + 1) / 2 || cnt2 >= (n + 1) / 2) {
return max(cnt1, cnt2);
}
int ans = count(all(a), 2);
auto solve = [&](int x) {
vector<int> cnt(n + 1), sum(n + 1), mn(n + 1);
for(int i = 0; i < n; i++) {
cnt[i + 1] = cnt[i] + (x == a[i]);
sum[i + 1] = sum[i] + (x == a[i] ? 1 : -1);
mn[i + 1] = min(mn[i], sum[i + 1]);
}
for(int i = 0; i <= n; i++) mn[i] = -mn[i];
int res = 0;
for(int r = 0; r <= n; r++) {
int l = lower_bound(all(mn), -sum[r]) - mn.begin();
if(l <= r) {
res = max(res, cnt[r] - (l > 0 ? cnt[l - 1] : 0));
}
}
return res;
};
return max({ans, solve(1), solve(3)});
}
