#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
int occ[maxn];
vector < pair < int, int > > ranges[maxn];
int sequence(int N, vector<int> A)
{
if (N > 2e3)
{
int len = 1;
for (int i = 1; i < N; i ++)
{
if (A[i] == A[i - 1])
len ++;
else
{
ranges[A[i - 1]].push_back({i - len, i - 1});
len = 1;
}
}
ranges[A[N - 1]].push_back({N - len, N - 1});
int ans = 1;
for (int i = 1; i <= N; i ++)
{
for (pair < int, int > cur : ranges[i])
ans = max(ans, cur.second - cur.first + 1);
if (ranges[i].size() == 2)
{
pair < int, int > lf, rf;
lf = ranges[i][0];
rf = ranges[i][1];
int big = rf.first - lf.second - 1;
int small = lf.first + N - rf.second - 1;
int mid = (lf.second - lf.first + 1 + rf.second - rf.first + 1);
if (big > small + mid)
continue;
///cout << i << " : " << small << " : " << big << " : " << mid << endl;
//cout << lf.first << " " << rf.second << endl;
ans = max(ans, mid);
}
}
return ans;
}
else
{
multiset < int > lf, rf;
int ans = 1;
for (int i = 0; i < N; i ++)
{
for (int j = 0; j <= N; j ++)
occ[j] = 0;
lf.clear();
rf.clear();
lf.insert(A[i]);
occ[A[i]] ++;
for (int j = i + 1; j < N; j ++)
{
occ[A[j]] ++;
if (A[j] > *lf.rbegin())
rf.insert(A[j]);
else
lf.insert(A[j]);
while(lf.size() > rf.size() + 1)
{
int x = *lf.rbegin();
lf.erase(lf.find(x));
rf.insert(x);
}
while(rf.size() > lf.size())
{
int x = *rf.begin();
rf.erase(rf.find(x));
lf.insert(x);
}
if ((j - i + 1) % 2 == 0)
{
ans = max(ans, occ[*lf.rbegin()]);
ans = max(ans, occ[*rf.begin()]);
}
else
{
ans = max(ans, occ[*lf.rbegin()]);
}
}
}
return ans;
}
}
