#include <bits/stdc++.h>
using namespace std;
struct node{
int x, y, type, val;
};
int st[8000005], n, ans = 1;
vector<node> qry, mergesort;
/*
void update(int id, int l, int r, int p, int v){
if(l == r) st[id] = min(st[id], v);
else{
int mid = (l + r) / 2;
if(p <= mid) update(id * 2, l, mid, p, v);
else update(id * 2 + 1, mid + 1, r, p, v);
st[id] = min(st[id * 2], st[id * 2 + 1]);
}
}
void del(int id, int l, int r, int p){
if(l == r) st[id] = 1e9;
else{
int mid = (l + r) / 2;
if(p <= mid) del(id * 2, l, mid, p);
else del(id * 2 + 1, mid + 1, r, p);
st[id] = min(st[id * 2], st[id * 2 + 1]);
}
}
int get(int id, int l, int r, int u, int v){
if(v < l || r < u) return 1e9;
if(u <= l && r <= v) return st[id];
int mid = (l + r) / 2;
return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}*/
int get(int l, int r){
int res = 1e9;
for(int i = l; i <= r; i++) res = min(res, st[i]);
return res;
}
void del(int p){
st[p] = 1e9;
}
void update(int p, int v){
st[p] = min(st[p], v);
}
void cdq(int l, int r){
if(l >= r) return;
int mid = (l + r) / 2;
cdq(l, mid);
cdq(mid + 1, r);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r){
if(qry[i].x <= qry[j].x){
if(qry[i].type == 1) update(qry[i].y, qry[i].val);
mergesort[k++] = qry[i++];
}else{
if(qry[j].type == 0) ans = max(ans, qry[j].val - get(1, qry[j].y) + 1);
mergesort[k++] = qry[j++];
}
}
while(j <= r){
if(qry[j].type == 0) ans = max(ans, qry[j].val - get(1, qry[j].y) + 1);
mergesort[k++] = qry[j++];
}
for(int p = l; p < i; p++){
if(qry[p].type == 1) del(qry[p].y);
}
while(i <= mid) mergesort[k++] = qry[i++];
for(int p = l; p <= r; p++) qry[p] = mergesort[p];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= 3 * n + 1; i++) st[i] = 1e9;
vector<vector<int>> pos(n + 1);
for(int i = 1; i <= n; i++) pos[a[i]].push_back(i);
vector<int> pre(n + 1);
for(int val = 1; val <= n; val++){
for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + (a[i] > val) - (a[i] < val);
vector<int> premn(n + 2), premx(n + 2);
for(int i = 1; i <= n; i++){
premn[i] = min(premn[i - 1], pre[i]);
premx[i] = max(premx[i - 1], pre[i]);
}
vector<int> sufmn(n + 2), sufmx(n + 2);
sufmn[n + 1] = 1e9, sufmx[n + 1] = -1e9;
for(int i = n; i >= 1; i--){
sufmn[i] = min(sufmn[i + 1], pre[i]);
sufmx[i] = max(sufmx[i + 1], pre[i]);
}
int sz = pos[val].size();
qry.clear();
for(int i = 0; i < sz; i++){
qry.push_back({i + premn[pos[val][i] - 1] + n, i - premx[pos[val][i] - 1] + n, 1, i}); //point update
qry.push_back({i + sufmx[pos[val][i]] + 1 + n, i - sufmn[pos[val][i]] + 1 + n, 0, i}); //range query
}
mergesort.resize(qry.size());
cdq(0, qry.size() - 1);
/*
for(int i = 1; i < qry.size(); i++){
for(int j = 0; j < i; j++){
if(qry[j].x <= qry[i].x && qry[j].y <= qry[i].y && qry[i].type == 0 && qry[j].type == 1){
ans = max(ans, qry[i].val - qry[j].val + 1);
}
}
}*/
}
cout << ans;
}
/*
sufmn[pos[val][j]] - premx[pos[val][i] - 1] <= j - i + 1;
premn[pos[val][i] - 1] - sufmx[pos[val][j]] <= j - i + 1;
//<=>
i - premx[pos[val][i] - 1] <= j - sufmn[pos[val][j]] + 1;
premn[pos[val][i] - 1] + i <= j + sufmx[pos[val][j]] + 1;*/
