#include <bits/stdc++.h>
using namespace std;
struct node{
int x, y, type, val;
};
int st[60000005], 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));
}
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(1, 1, 3 * n, qry[i].y, qry[i].val);
mergesort[k++] = qry[i++];
}else{
if(qry[j].type == 0) ans = max(ans, qry[j].val - get(1, 1, 3 * n, 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, 1, 3 * n, 1, qry[j].y) + 1);
mergesort[k++] = qry[j++];
}
for(int p = l; p < i; p++){
if(qry[p].type == 1) del(1, 1, 3 * n, qry[p].y);
}
while(i <= mid) mergesort[k++] = qry[i++];
for(int p = l; p <= r; p++) qry[p] = mergesort[p];
}
int sequence(int x, vector<int> c){
n = x;
vector<int> a(n + 1), pre(n + 1);
for(int i = 1; i <= n; i++) a[i] = c[i - 1];
vector<vector<int>> pos(n + 1);
for(int i = 1; i <= n; i++) pos[a[i]].push_back(i);
for(int i = 1; i < 60000005; i++) st[i] = 1e9;
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);
}
return ans;
}
#ifdef LOCAL
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> a(n);
for(int &x: a) cin >> x;
cout << sequence(n, a);
}
#endif LOCAL
