#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
const int X = 10;
int sequence(int N, std::vector<int> A) {
int f[X+1][N+1] = {};
A.insert(A.begin() , 0);
for (int i = 1; i <= N ; i++){
f[A[i]][i]++;
for (int j =1 ; j <= X ; j++){
f[j][i] += f[j][i-1];
}
}
int mx = 0;
for (int m = 1 ; m <= X ; m++){
int v[2][N+1] = {};
for (int i = 1 ; i <= N ; i++){
for (int j = 1; j <= X ; j++){
v[0][i] += (j <= m ? f[j][i] : -f[j][i]);
v[1][i] += (j >= m ? f[j][i] : -f[j][i]);
}
}
int suf[2][N+2] = {};
suf[0][N+1] = -1e9;
suf[1][N+1] = -1e9;
for (int i = N ; i > 0 ; i--) suf[0][i] = max(suf[0][i+1] , v[0][i]);
for (int i = N ; i > 0 ; i--) suf[1][i] = max(suf[1][i+1] , v[1][i]);
for (int l = 1 ; l <= N ; l++){
int L = l , R = N , md , ans = -1;
while(L<=R){
md = (L+R)/2;
if (suf[0][md] >= v[0][l-1] && suf[1][md] >= v[1][l-1]) L = md+1 , ans = md;
else R = md-1;
}
//cout << m << ' ' << l << ' ' << ans << ' ' << suf[0][ans] << ' ' << v[0][l-1] << '\n';
if (ans != -1) mx = max(mx , f[m][ans] - f[m][l-1]);
}
}
return mx;
}
