#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int,int>
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;
const int mn = 5e5 + 5;
const int mod = 1000000007LL, inf = 2e18;
struct SegTree{
pii st[mn << 2];
int lz[mn << 2];
pii merge(pii a, pii b){
return {min(a.fi, b.fi), max(a.se, b.se)};
}
void build(int id, int l, int r){
if(l == r){
st[id] = {-l, -l};
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
void down(int id){
if(!lz[id]) return;
st[id << 1].fi += lz[id], st[id << 1].se += lz[id];
lz[id << 1] += lz[id];
st[id << 1 | 1].fi += lz[id], st[id << 1 | 1].se += lz[id];
lz[id << 1 | 1] += lz[id];
lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val){
if(l > v || r < u) return;
if(l >= u && r <= v){
st[id].fi += val, st[id].se += val;
lz[id] += val;
return;
}
down(id);
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
pii get(int id, int l, int r, int u, int v){
if(l > v || r < u) return {inf, - inf};
if(l >= u && r <= v) return st[id];
down(id);
int mid = (l + r) >> 1;
return merge(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
} pre, suf;
int n, a[mn], min_val[2][mn], max_val[2][mn];
vector <int> pos[mn];
bool check(int mid){
for(int i = 1; i <= n; i++){
if(pos[i].size() < mid) continue;
for(int j = 0; j < pos[i].size() - mid + 1; j++){
int l = pos[i][j], r = pos[i][j + mid - 1];
if(min_val[1][r] - max_val[0][l] <= 0 && max_val[1][r] - min_val[0][l] >= 0) return true;
}
}
return false;
}
int sequence(int N, std::vector<int> A){
n = N;
for(int i = 1; i <= n; i++){
a[i] = A[i - 1];
pos[a[i]].push_back(i);
}
pre.build(1, 0, n); suf.build(1, 0, n);
for(int i = 1; i <= n; i++){
for(auto p : pos[i]) suf.update(1, 0, n, p, n, 2);
for(auto p : pos[i]){
min_val[0][p] = suf.get(1, 0, n, 0, p - 1).fi, max_val[0][p] = pre.get(1, 0, n, 0, p - 1).se;
min_val[1][p] = pre.get(1, 0, n, p, n).fi, max_val[1][p] = suf.get(1, 0, n, p, n).se;
}
for(auto p : pos[i]) pre.update(1, 0, n, p, n, 2);
}
int l = 1, r = n, ans = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)){
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
return ans;
}
// void solve(){
// int N; cin >> N;
// vector <int> A(N);
// for(int i = 0; i < N; i++) cin >> A[i];
// cout << sequence(N, A);
// }
// // Waifu of the day: Kagari Fuyukawa
// signed main(){
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// if(fopen("mario.inp", "r")){
// freopen("mario.inp", "r", stdin);
// freopen("mario.out", "w", stdout);
// }
// int t = 1;
// // cin >> t;
// while(t--) solve();
// }
