#include "sequence.h"

#include <vector>
#include <algorithm>

using namespace std;

const int INF = (int)1e9;

int solve(int N, vector<int> A){
  int pref[N], cnt[N];
  for(int i = 0; i < N; i++)
    pref[i] = (A[i] == 1 ? 1 : -1) + (i > 0 ? pref[i - 1] : 0);
  for(int i = 0; i < N; i++)
    cnt[i] = (i > 0 ? cnt[i - 1] : 0) + (A[i] == 1);
  int mx[N], res = 0;
  for(int i = N - 1; i >= 0; i--)
    mx[i] = max((i + 1 < N ? mx[i + 1] : -INF), pref[i]);
  for(int i = N - 2; i >= -1; i--){
    int at_least = (i >= 0 ? pref[i] : 0);
    int l = i + 1, r = N;
    while(r - l > 1){
      int mid = (l + r) / 2;
      if(mx[mid] >= at_least) l = mid;
      else r = mid;
    }
    if(mx[l] >= at_least) res = max(res, cnt[l] - (i >= 0 ? cnt[i] : 0));
  }
  return res;
}

int sequence(int N, std::vector<int> A) {
  vector<int> B = A;
  sort(A.begin(), A.end());
  if(A[N - 1] <= 2){
    int c1 = 0, c2 = 0;
    for(int i = 0; i < N; i++)
      c1 += (A[i] == 1), c2 += (A[i] == 2);
    return max(c1, c2);
  }
  vector<int> medians;
  if(N % 2 == 1) medians = {A[N / 2]};
  else medians = {A[N / 2 - 1], A[N / 2]};
  int res = 0;
  for(int x : medians){
    int cnt = 0;
    for(int j = 0; j < N; j++)
      cnt += (A[j] == x);
    res = max(res, cnt);
  }
  res = max(res, solve(N, B));
  for(int i = 0; i < (int)B.size(); i++)
    B[i] = 4 - B[i];
  res = max(res, solve(N, B));
  return res;
}