#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using o_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
int sequence(int N, vector<int> A) {
int mx = 0;
for(int i = 0; i < N;)
{
int j = i;
while(j < N and A[j] == A[i])
j++;
mx = max(mx, j - i);
i = j;
}
vector<int> in(N + 1, -1), out(N + 1, -1);
vector<int> occ(N + 1, 0);
for(int i = 0; i < N; i++)
{
if(in[A[i]] == -1)
in[A[i]] = i;
out[A[i]] = i;
occ[A[i]]++;
}
for(int i = 1; i <= N; i++)
{
int idx = occ[i] - 1;
idx += in[i];
idx += N - out[i] - 1;
if(idx >= (N - 1) / 2)
{
mx = max(mx, occ[i]);
}
}
return mx;
}
