#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 5e5 + 5;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
int n, a[lim];
namespace sub12{
int solve(){
vector<int>bit(n + 1);
function<void(int)>update = [&] (int p){
for(; p <= n; p += p & -p){
bit[p]++;
}
};
function<int(int)>get = [&] (int p){
int ans = 0;
for(; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
};
int ans = 0;
for(int i = 1; i <= n; i++){
fill(bit.begin(), bit.end(), 0);
for(int j = i; j <= n; j++){
update(a[j]);
int low = 1, high = n, x = j - i + 1, median;
while(low <= high){
int mid = (low + high) >> 1;
if(get(mid) >= (x >> 1) + (x & 1)){
high = (median = mid) - 1;
}
else{
low = mid + 1;
}
}
maximize(ans, get(median) - get(median - 1));
if((~x & 1) && get(median) == (x >> 1)){
low = median + 1;
high = n;
while(low <= high){
int mid = (low + high) >> 1;
if(get(mid) > (x >> 1)){
high = (median = mid) - 1;
}
else{
low = mid + 1;
}
}
maximize(ans, get(median) - get(median - 1));
}
}
}
return ans;
}
}
namespace sub4{
int solve(){
vector<int>_a;
for(int i = 1; i <= n; i++){
_a.push_back(a[i]);
}
sort(_a.begin(), _a.end());
if(_a[n >> 1] != 2 || _a[(n - 1) >> 1] != 2){
return count(a + 1, a + n + 1, _a[n >> 1]);
}
int ans = count(a + 1, a + n + 1, 2);
vector<int>bit((n << 1) + 5, 0);
auto update = [&] (int p, int x){
for(p += n + 1; p < bit.size(); p += p & -p){
minimize(bit[p], x);
}
};
auto get = [&] (int p){
int ans = n;
for(p += n + 1; p > 0; p -= p & -p){
minimize(ans, bit[p]);
}
return ans;
};
for(int z = 0; z < 2; z++){
for(int i = 1; i <= n; i++){
if(a[i] == 1 || a[i] == 3){
a[i] ^= 2;
}
}
fill(bit.begin(), bit.end(), n);
update(0, 0);
for(int i = 1, f = 0; i <= n; update(f, i++)){
maximize(ans, (i - get(f += a[i] == 1 ? 1 : -1) + 1) >> 1);
}
}
return ans;
}
}
namespace sub3567{
const int INF = 1e9;
struct SegmentTree{
bool get_min;
int st[lim << 2], lazy[lim << 2];
void build(int id, int l, int r){
st[id] = get_min ? l : r;
lazy[id] = 0;
if(l < r){
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
}
}
void init(bool get_min){
this->get_min = get_min;
build(1, 0, n);
}
void propagate(int id, int x){
st[id] += x;
lazy[id] += x;
}
void push_down(int id){
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = get_min ? min(st[id << 1], st[id << 1 | 1]) : max(st[id << 1], st[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v){
if(l > v || r < u){
return get_min ? INF : -INF;
}
if(u <= l && v >= r){
return st[id];
}
push_down(id);
int m = (l + r) >> 1, left = get(id << 1, l, m, u, v), right = get(id << 1 | 1, m + 1, r, u, v);
return get_min ? min(left, right) : max(left, right);
}
};
SegmentTree st_min_1, st_max_1, st_min_2, st_max_2;
bool check(int l, int r){
return ll(st_max_1.get(1, 0, n, r, n) - st_min_1.get(1, 0, n, 0, l - 1)) * (st_min_2.get(1, 0, n, r, n) - st_max_2.get(1, 0, n, 0, l - 1)) < 1;
}
vector<int>pos[lim];
int solve(){
st_min_1.init(true);
st_max_1.init(false);
st_min_2.init(true);
st_max_2.init(false);
for(int i = 1; i <= n; i++){
pos[a[i]].push_back(i);
}
int ans = 0;
for(int x = 1; x <= n; x++){
for(int& i : pos[x]){
st_min_2.update(1, 0, n, i, n, -2);
st_max_2.update(1, 0, n, i, n, -2);
}
for(int l = 0, r = 0; l < pos[x].size(); l++){
maximize(r, l);
while(r < pos[x].size() && check(pos[x][l], pos[x][r])){
r++;
}
maximize(ans, r - l);
}
for(int& i : pos[x]){
st_min_1.update(1, 0, n, i, n, -2);
st_max_1.update(1, 0, n, i, n, -2);
}
}
return ans;
}
}
int sequence(int _n, vector<int>_a){
for(int i = n = _n; i > 0; i--){
a[i] = _a[i - 1];
}
if(n <= 2000){
return sub12::solve();
}
if(*max_element(a + 1, a + n + 1) <= 3){
return sub4::solve();
}
return sub3567::solve();
}
