#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)5e5 + 7;
int n, a[N];
namespace SUB1 {
struct CTDL {
multiset<int> a, b;
void add(int x) {
if (sz(a) <= sz(b)) a.insert(x);
else b.insert(x);
if (sz(a) and sz(b) and *a.rbegin()>*b.begin()){
int x=*a.rbegin(), y=*b.begin();
a.erase(a.find(x));
b.erase(b.find(y));
a.insert(y);
b.insert(x);
}
}
int med() {
return *a.rbegin();
}
int med2() {
return *b.begin();
}
};
int sol() {
int ans = 0;
vec<int> cnt(n + 1, 0);
FOR(i, 1, n) {
CTDL s;
FOR(j, i, n) {
++cnt[a[j]];
s.add(a[j]);
ans = max(ans, cnt[s.med()]);
if ( (j - i + 1) % 2 == 0 )
ans = max(ans, cnt[s.med2()]);
}
FOR(j, i, n) {
--cnt[a[j]];
}
}
return ans;
}
};
int sequence(int N, vector<int> A) {
n = N;
FOR(i, 1, n) a[i] = A[i - 1];
if (n <= 2000) {
return SUB1::sol();
}
return 0;
}
#ifdef LOCAL
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
int n; cin >> n;
vector<int> a(n);
for(int & x : a) cin >> x;
cout << sequence(n, a);
}
#endif LOCAL
