#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
int mid(vector<int> A)
{
sort(A.begin() , A.end());
return A[((int)A.size() - 1)/2];
}
struct segTree
{
int BASE;
vector<int> tree;
segTree(int n)
{
BASE = 2*n + 1;
while(__builtin_popcount(BASE) != 1)
BASE++;
tree.assign(2*BASE , BASE);
}
void upd(int i , int x)
{
if(tree[i + BASE] <= x)
return;
tree[i + BASE] = x;
for(int j = (i + BASE) / 2 ; j >= 1 ; j>>=1)
{
tree[j] = min(tree[j<<1] , tree[j<<1|1]);
}
}
int query(int l , int r)
{
l+=BASE;
r+=BASE;
if(l == r)
return tree[l];
int mn = min(tree[l] , tree[r]);
while(l + 1 < r)
{
if(l%2 == 0)
{
mn = min(mn , tree[l + 1]);
}
if(r%2 == 1)
{
mn = min(mn , tree[r - 1]);
}
l>>=1;
r>>=1;
}
return mn;
}
};
int getMax(int N , vector<int> A)
{
segTree tree(N);
tree.upd(0 + N, 0);
int ans = 0;
for(int i = 1 ; i <= N ; i++)
{
int mn = tree.query(0 , A[i] + N);
ans = max(ans , (i + A[i] - mn)/2);
tree.upd(A[i] + N , i + A[i]);
}
return ans;
}
int sequence(int N, std::vector<int> A)
{
int m = mid(A);
if(m != 2)
{
return count(A.begin() , A.end() , m);
}
int mx = count(A.begin() , A.end() , m);
vector<int> pref(N + 1);
for(int i = 0 ; i < N ; i++)
{
pref[i + 1] = (A[i] == 1 ? 1 : -1) + pref[i];
}
mx = max(mx , getMax(N , pref));
pref = vector<int>(N + 1);
for(int i = 0 ; i < N ; i++)
{
pref[i + 1] = (A[i] == 3 ? 1 : -1) + pref[i];
}
mx = max(mx , getMax(N , pref));
return mx;
}
