#include "sequence.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
multiset<ll>m1, m2;
ll med1()
{
return *(--m1.end());
}
ll med2()
{
return *m2.begin();
}
void bal()
{
while (m1.size()>m2.size()+1)
{
m2.insert(*(--m1.end()));
m1.erase((--m1.end()));
}
while (m2.size()>m1.size())
{
m1.insert(*m2.begin());
m2.erase(m2.begin());
}
}
void add(ll x)
{
if (m1.empty() or *(--m1.end())>=x)
m1.insert(x);
else
m2.insert(x);
bal();
}
int sequence(int N, std::vector<int> A) {
ll n = N;
vector<ll>v;
v.push_back(0);
for (int i=0 ; i<n ; i++)
v.push_back(A[i]);
ll res = 0;
for (int i=1 ; i<=n ;i++)
{
map<ll,ll>frq;
m1.clear();
m2.clear();
for (int j=i ; j<=n ;j++)
{
add(v[j]);
frq[v[j]]++;
if ((j-i+1)%2)
res = max(res, frq[med1()]);
else
res = max({res, frq[med1()], frq[med2()]});
}
}
return res;
}
/*
9
1 1 2 3 4 3 2 1 1
*/
