#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
vector <int> pos[N];
int mn[4 * N], mx[4 * N], lz[4 * N];
void build(int s, int l, int r){
if (l == r){
mn[s] = l;
mx[s] = l;
return;
}
int mid = l + r >> 1;
build(2 * s, l, mid);
build(2 * s + 1, mid + 1, r);
mn[s] = min(mn[2 * s], mn[2 * s + 1]) + lz[s];
mx[s] = max(mx[2 * s], mx[2 * s + 1]) + lz[s];
}
void upd(int s, int l, int r, int u, int v, int val){
if (u <= l && r <= v){
mn[s] += val;
mx[s] += val;
lz[s] += val;
return;
}
int mid = l + r >> 1;
if (mid >= u) upd(2 * s, l, mid, u, v, val);
if (mid + 1 <= v) upd(2 * s + 1, mid + 1, r, u, v, val);
mn[s] = min(mn[2 * s], mn[2 * s + 1]) + lz[s];
mx[s] = max(mx[2 * s], mx[2 * s + 1]) + lz[s];
}
int getMin(int s, int l, int r, int u, int v){
if (r < u || l > v) return 1e9;
if (u <= l && r <= v) return mn[s];
int mid = l + r >> 1;
return min(getMin(2 * s, l, mid, u, v), getMin(2 * s + 1, mid + 1, r, u, v)) + lz[s];
}
int getMax(int s, int l, int r, int u, int v){
if (r < u || l > v) return -1e9;
if (u <= l && r <= v) return mx[s];
int mid = l + r >> 1;
return max(getMax(2 * s, l, mid, u, v), getMax(2 * s + 1, mid + 1, r, u, v)) + lz[s];
}
int sequence(int n, vector <int> a){
for (int i = 0; i < n; ++ i) pos[a[i]].push_back(i + 1);
build(1, 0, n);
int res = 1;
for (int i = 1; i <= n; ++ i){
vector <int> mx_sf, mn_pf;
for (int j : pos[i]){
mx_sf.push_back(getMax(1, 0, n, j, n));
mn_pf.push_back(getMin(1, 0, n, 0, j - 1));
}
for (int j : pos[i]) upd(1, 0, n, j, n, -2);
vector <int> mn_sf, mx_pf;
for (int j : pos[i]){
mn_sf.push_back(getMin(1, 0, n, j, n));
mx_pf.push_back(getMax(1, 0, n, 0, j - 1));
}
for (int j = pos[i].size() - 1; j >= 0; -- j){
while (j + res < pos[i].size()){
if (mn_pf[j] <= mx_sf[j + res] && mn_sf[j + res] <= mx_pf[j]) ++ res;
else break;
}
}
}
return res;
}
