#include "sequence.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
using namespace std;
const int INF = 1e9 + 7;
const int N = 5e5 + 5;
int a[N];
int p1[N];
int p2[N];
int p3[N];
int v1[N];
int v2[N];
int v3[N];
int v4[N];
int seg1[N << 2];
int seg2[N << 2];
int seg3[N << 2];
int seg4[N << 2];
void build1(int nd, int s, int e){
if(s == e){
seg1[nd] = v1[s];
return;
}
int mid = s + e >> 1;
build1(nd << 1, s, mid);
build1(nd << 1 | 1, mid + 1, e);
seg1[nd] = max(seg1[nd << 1], seg1[nd << 1 | 1]);
}
void build2(int nd, int s, int e){
if(s == e){
seg2[nd] = v2[s];
return;
}
int mid = s + e >> 1;
build2(nd << 1, s, mid);
build2(nd << 1 | 1, mid + 1, e);
seg2[nd] = max(seg2[nd << 1], seg2[nd << 1 | 1]);
}
void build3(int nd, int s, int e){
if(s == e){
seg3[nd] = v3[s];
return;
}
int mid = s + e >> 1;
build3(nd << 1, s, mid);
build3(nd << 1 | 1, mid + 1, e);
seg3[nd] = max(seg3[nd << 1], seg3[nd << 1 | 1]);
}
void build4(int nd, int s, int e){
if(s == e){
seg4[nd] = v4[s];
return;
}
int mid = s + e >> 1;
build4(nd << 1, s, mid);
build4(nd << 1 | 1, mid + 1, e);
seg4[nd] = max(seg4[nd << 1], seg4[nd << 1 | 1]);
}
int qry1(int nd, int s, int e, int pos, int val){
if(s > pos) return -1;
if(s == e) return s;
int mid = s + e >> 1;
if(seg1[nd << 1] >= val) return qry1(nd << 1, s, mid, pos, val);
else return qry1(nd << 1 | 1, mid + 1, e, pos, val);
}
int qry2(int nd, int s, int e, int pos, int val){
if(s > pos) return -1;
if(s == e) return s;
int mid = s + e >> 1;
if(seg2[nd << 1] >= val) return qry2(nd << 1, s, mid, pos, val);
else return qry2(nd << 1 | 1, mid + 1, e, pos, val);
}
int qry3(int nd, int s, int e, int pos, int val){
if(s > pos) return -1;
if(s == e) return s;
int mid = s + e >> 1;
if(seg3[nd << 1] >= val) return qry3(nd << 1, s, mid, pos, val);
else return qry3(nd << 1 | 1, mid + 1, e, pos, val);
}
int qry4(int nd, int s, int e, int pos, int val){
if(s > pos) return -1;
if(s == e) return s;
int mid = s + e >> 1;
if(seg4[nd << 1] >= val) return qry4(nd << 1, s, mid, pos, val);
else return qry4(nd << 1 | 1, mid + 1, e, pos, val);
}
int sequence(int n, vector<int> A) {
int ans = 1;
for(int i = 1;i<=n;++i) a[i] = A[i - 1];
for(int i = 1;i<=n;++i){
p1[i] = p1[i - 1] + (a[i] == 1);
p2[i] = p2[i - 1] + (a[i] == 2);
p3[i] = p3[i - 1] + (a[i] == 3);
v1[i] = p3[i] + p2[i] - p1[i];
v2[i] = p1[i] + p2[i] - p3[i];
v3[i] = p3[i] - p1[i] - p2[i];
v4[i] = p1[i] - p3[i] - p2[i];
}
build1(1, 1, n);
build2(1, 1, n);
build3(1, 1, n);
build4(1, 1, n);
for(int i = 2;i<=n;++i){
int r1 = qry1(1, 1, n, i - 1, v1[i]);
int r2 = qry2(1, 1, n, i - 1, v2[i]);
int r3 = qry3(1, 1, n, i - 1, v3[i]);
int r4 = qry4(1, 1, n, i - 1, v4[i]);
if(r1 > 0) ans = max(ans, p1[i] - p1[r1]);
if(r3 > 0) ans = max(ans, p2[i] - p2[r3]);
if(r4 > 0) ans = max(ans, p2[i] - p2[r4]);
if(r2 > 0) ans = max(ans, p3[i] - p3[r2]);
if(p1[i] >= p2[i] + p3[i]) ans = max(ans, p1[i]);
if(p3[i] >= p1[i] + p2[i]) ans = max(ans, p3[i]);
if(p2[i] >= abs(p1[i] - p3[i])) ans = max(ans, p2[i]);
}
return ans;
}
/*
7
1 2 3 1 2 1 3
9
1 1 2 3 4 3 2 1 1
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/
