#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];
}
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){
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 + 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();
qry.clear();
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);
qry.push_back({i + premn + n, i - premx + n, 1, i}); //point update
qry.push_back({i + sufmx + 1 + n, i - sufmn + 1 + n, 0, i}); //range query
}
mergesort.resize(qry.size());
cdq(0, qry.size() - 1);
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;
}
