#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int seg[N * 4];
void Build(int l, int r, int pos)
{
seg[pos] = 0;
if(l == r) return;
int mid = (l + r) / 2;
Build(l, mid, pos * 2);
Build(mid + 1, r, pos * 2 + 1);
}
void Update(int l, int r, int pos, int qpos, int qval)
{
seg[pos] += qval;
if(l == r) return;
int mid = (l + r) / 2;
if(qpos <= mid)
{
Update(l, mid, pos * 2, qpos, qval);
}
else
{
Update(mid + 1, r, pos * 2 + 1, qpos, qval);
}
}
int Query(int l, int r, int pos, int qval)
{
if(l == r)
{
return seg[pos];
}
int mid = (l + r) / 2;
if(seg[pos * 2] >= qval)
{
return Query(l, mid, pos * 2, qval);
}
else
{
return Query(mid + 1, r, pos * 2 + 1, qval - seg[pos * 2]);
}
}
int sequence(int n, vector<int> a)
{
int ans = 0;
for(int i = 0; i < n; i++)
{
Build(1, n, 1);
for(int j = i; j < n; j++)
{
Update(1, n, 1, a[j], 1);
int len = j - i + 1;
int median = (len + 1) / 2;
ans = max(ans, Query(1, n, 1, median));
median = (len + 2) / 2;
ans = max(ans, Query(1, n, 1, median));
}
}
return ans;
}
