#include <bits/stdc++.h>
using namespace std;
struct node{
int x, y, type, val;
};
int st[60000005];
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));
}
struct SegmentTree{
vector<int> mn, mx, lazy;
void init(int n){
mn.resize(4 * n + 5);
mx.resize(4 * n + 5);
lazy.resize(4 * n + 5, 0);
build(1, 0, n);
}
void build(int id, int l, int r){
if(l == r){
mn[id] = mx[id] = l;
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
mn[id] = min(mn[id * 2], mn[id * 2 + 1]);
mx[id] = max(mx[id * 2], mx[id * 2 + 1]);
}
void apply(int id, int val){
mn[id] += val;
mx[id] += val;
lazy[id] += val;
}
void push(int id){
apply(id * 2, lazy[id]);
apply(id * 2 + 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val){
if(v < l || r < u) return;
if(u <= l && r <= v) apply(id, val);
else{
push(id);
int mid = (l + r) / 2;
update(id * 2, l, mid, u, v, val);
update(id * 2 + 1, mid + 1, r, u, v, val);
mn[id] = min(mn[id * 2], mn[id * 2 + 1]);
mx[id] = max(mx[id * 2], mx[id * 2 + 1]);
}
}
pair<int, int> merge(pair<int, int> a, pair<int, int> b){
return {min(a.first, b.first), max(a.second, b.second)};
}
pair<int, int> query(int id, int l, int r, int u, int v){
if(v < l || r < u) return {1e9, -1e9};
if(u <= l && r <= v) return {mn[id], mx[id]};
push(id);
int mid = (l + r) / 2;
return merge(query(id * 2, l, mid, u, v), query(id * 2 + 1, mid + 1, r, u, v));
}
} seg;
int sequence(int x, vector<int> c){
int n = x, ans = 1;
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 + 2);
for(int i = 1; i <= n; i++) pos[a[i]].push_back(i);
for(int i = 1; i < 60000005; i++) st[i] = 1e9;
seg.init(n);
for(int x: pos[1]) seg.update(1, 0, n, x, n, -1);
for(int val = 1; val <= n; val++){
int sz = pos[val].size();
vector<node> diddy;
for(int i = 0; i < sz; i++){
auto [premn, premx] = seg.query(1, 0, n, 0, pos[val][i] - 1);
auto [sufmn, sufmx] = seg.query(1, 0, n, pos[val][i], n);
diddy.push_back({i + premn + n, i - premx + n, 0, i}); //point update
diddy.push_back({i + sufmx + 1 + n, i - sufmn + 1 + n, 1, i}); //range query
}
sort(diddy.begin(), diddy.end(), [&](node a, node b){
return a.x < b.x || (a.x == b.x && a.type < b.type);
});
for(auto [x, y, type, val]: diddy){
if(type == 0) update(1, 1, 3 * n, y, val);
else ans = max(ans, val - get(1, 1, 3 * n, 1, y) + 1);
}
for(auto [x, y, type, val]: diddy) del(1, 1, 3 * n, y);
for(int x: pos[val]) seg.update(1, 0, n, x, n, -1);
for(int x: pos[val + 1]) seg.update(1, 0, n, x, n, -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
