/*
written by sim_ple
*/
#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
// #define int long long
#define N 500005
#define itn int
#define all(x) x.begin() , x.end()
int pref1[N] , pref2[N] , pref3[N];
int v1[N] , v2[N] , v3[N] , v4[N];
int mx1[N << 2] , mx2[N << 2] , mx3[N << 2] , mx4[N << 2];
void build1(int node , int l , int r){
if(l == r){
mx1[node] = v1[l];
return;
}
int md = (l + r) / 2;
build1(node << 1 , l , md);
build1(node << 1 | 1 , md + 1 , r);
mx1[node] = max(mx1[node << 1] , mx1[node << 1 | 1]);
}
void build2(int node , int l , int r){
if(l == r){
mx2[node] = v2[l];
return;
}
int md = (l + r) / 2;
build2(node << 1 , l , md);
build2(node << 1 | 1 , md + 1 , r);
mx2[node] = max(mx2[node << 1] , mx2[node << 1 | 1]);
}
void build3(int node , int l , int r){
if(l == r){
mx3[node] = v3[l];
return;
}
int md = l + r >> 1;
build3(node << 1 , l , md);
build3(node << 1 | 1 , md + 1 , r);
mx3[node] = max(mx3[node << 1] , mx3[node << 1 | 1]);
}
void build4(int node , int l , int r){
if(l == r){
mx4[node] = v4[l];
return;
}
int md = l + r >> 1;
build4(node << 1 , l , md);
build4(node << 1 | 1 , md + 1 , r);
mx4[node] = max(mx4[node << 1] , mx4[node << 1 | 1]);
}
int find1(int node , int l , int r, int idx , int val){
if(l > idx) return -1;
if(l == r) return l;
int md = l + r >> 1;
if(mx1[node << 1] >= val){
return find1(node << 1 , l , md , idx , val);
}
else{
return find1(node << 1 | 1 , md + 1 , r , idx , val);
}
}
int find2(int node , int l , int r, int idx , int val){
if(l > idx) return -1;
if(l == r) return l;
int md = l + r >> 1;
if(mx2[node << 1] >= val){
return find2(node << 1 , l , md , idx , val);
}
else{
return find2(node << 1 | 1 , md + 1 , r , idx , val);
}
}
int find3(int node , int l , int r, int idx , int val){
if(l > idx) return -1;
if(l == r) return l;
int md = l + r >> 1;
if(mx3[node << 1] >= val){
return find3(node << 1 , l , md , idx , val);
}
else{
return find3(node << 1 | 1 , md + 1 , r , idx , val);
}
}
int find4(int node , int l , int r , int idx , int val){
if(l > idx) return -1;
if(l == r) return l;
int md = l + r >> 1;
if(mx4[node << 1] >= val){
return find4(node << 1 , l , md , idx ,val);
}
else{
return find4(node << 1 | 1 , md + 1 , r , idx , val);
}
}
int sequence(int n , vector<int> a){
for(int i = 1; i <= n; i++){
pref1[i] = pref1[i - 1] + (a[i - 1] == 1);
pref2[i] = pref2[i - 1] + (a[i - 1] == 2);
pref3[i] = pref3[i - 1] + (a[i - 1] == 3);
v1[i] = pref2[i] + pref3[i] - pref1[i];
v2[i] = pref1[i] + pref2[i] - pref3[i];
v3[i] = pref3[i] - pref1[i] - pref2[i];
v4[i] = pref1[i] - pref3[i] - pref2[i];
}
build1(1 , 1 , n);
build2(1 , 1 , n);
build3(1 , 1 , n);
build4(1 , 1 , n);
int ans = 1;
for(int i = 2; i <= n; i++){
int r1 = find1(1 , 1 , n , i - 1 , v1[i]);
int r2 = find2(1 , 1 , n , i - 1 , v2[i]);
int r3 = find3(1 , 1 , n , i - 1 , v3[i]);
int r4 = find4(1 , 1 , n , i - 1 , v4[i]);
if(r1 > 0) ans = max(ans , pref1[i] - pref1[r1]);
if(r3 > 0) ans = max(ans , pref2[i] - pref2[r3]);
if(r4 > 0) ans = max(ans , pref2[i] - pref2[r4]);
if(r2 > 0) ans = max(ans , pref3[i] - pref3[r2]);
if(pref1[i] >= pref2[i] + pref3[i]) ans = max(ans , pref1[i]);
if(pref3[i] >= pref1[i] + pref2[i]) ans = max(ans , pref3[i]);
if(pref2[i] >= abs(pref1[i] - pref3[i])) ans = max(ans , pref2[i]);
}
return ans;
}
// void solve1(){
// int n;
// cin >> n;
// vector<int> a(n + 1);
// for(int i = 0; i < n; i++){
// cin >> a[i];
// }
// cout << sequence(n , a) << endl;
// }
// int32_t main() {
// ios::sync_with_stdio(0); cin.tie(0);
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
// int t = 1;
// //cin >> t;
// while(t--) solve1();
// return 0;
// }
