#include "sequence.h"
#include <bits/extc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int32_t, int32_t>
#define tiii tuple <int32_t, int32_t, int32_t>
#define all(a) a.begin(), a.end()
using namespace std;
using namespace __gnu_pbds;
#define ordered_multiset tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
const int N = 3e6 + 5;
const int inf = 1e18;
int n, a[N], fenwick[4][N];
void update(int idx, int num, int val){
while (idx < N) {
fenwick[num][idx] = min(fenwick[num][idx], val);
idx += idx & -idx;
}
}
int query(int num, int idx){
int mx = inf;
while (idx > 0) {
mx = min(mx, fenwick[num][idx]);
idx -= idx & -idx;
}
return mx;
}
int32_t sequence(int32_t Nn, vector<int32_t> A) {
for (int i = 1; i < N; i++) fenwick[1][i] = fenwick[3][i] = inf;
n = Nn;
int freq[4][n + 1]; memset(freq, 0, sizeof freq);
for (int i = 0; i < n; i++) {
a[i + 1] = A[i];
for (int j = 1; j <= 3; j++) {
freq[j][i + 1] = freq[j][i] + (A[i] == j);
}
}
int ans = freq[2][n];
for (int i = 1; i <= 3; i++) {
if (i == 2) continue;
for (int j = 1; j <= n; j++) {
if (a[j] != i) continue;
if (2 * freq[i][j] >= j) ans = max(ans, freq[i][j]);
ans = max(ans, freq[i][j] - query(i, 2 * freq[i][j] - j + (N/2)));
update(2 * freq[i][j] - j + (N/2), i, freq[i][j]);
}
}
return ans;
}
