#include "sequence.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
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 mx = 0;
for (int i=1 ; i<=n ;i++)
{
vector<ll>cnt(n+1, 0);
for (int j=1 ; j<=n ; j++)
{
cnt[j] = (v[j]==v[i]);
cnt[j] += cnt[j-1];
}
vector<ll>pref(n+1, 0);
for (int j=1 ; j<=n ; j++)
{
if (v[j]>v[i])
pref[j] = 1;
if (v[j]<v[i])
pref[j] = -1;
if (v[j]==v[i])
pref[j] = 0;
pref[j] += pref[j-1];
}
map<ll,ll>frs;
for (int j=1 ; j<=n ; j++)
{
if (pref[j]==0) {mx = max(mx, cnt[j]); continue;}
if (frs[pref[j]]==0) frs[pref[j]] = j;
else
mx = max(mx, cnt[j]-cnt[frs[pref[j]]]);
}
for (int j=1 ; j<=n ;j++)
{
if (v[j]>v[i])
pref[j] = 1;
else
pref[j] = -1;
pref[j] += pref[j-1];
}
frs.clear();
for (int j=1 ; j<=n ; j++)
{
if (pref[j]==0) {mx = max(mx, cnt[j]); continue;}
if (frs[pref[j]]==0) frs[pref[j]] = j;
else
mx = max(mx, cnt[j]-cnt[frs[pref[j]]]);
}
for (int j=1 ; j<=n ;j++)
{
if (v[j]>=v[i])
pref[j] = 1;
else
pref[j] = -1;
pref[j] += pref[j-1];
}
frs.clear();
for (int j=1 ; j<=n ; j++)
{
if (pref[j]==0) {mx = max(mx, cnt[j]); continue;}
if (frs[pref[j]]==0) frs[pref[j]] = j;
else
mx = max(mx, cnt[j]-cnt[frs[pref[j]]]);
}
}
return mx;
}
/*
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/
