#include "sequence.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
#define fore(i, l, r) for (ll i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (ll i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }
const int INF = 1e18 + 7;
struct SegTreeLazy {
vector<array<ll, 2>> mn, mx;
vll lz;
ll n;
SegTreeLazy () { }
SegTreeLazy (ll n): n(n), mn(4*n+4, {0, 0}), mx(4*n+4, {0, 0}), lz(4*n+4, 0) { }
void build (ll id, ll l, ll r) {
if (l==r) {
mn[id] = {0, l};
mx[id] = {0, l};
return;
}
ll m = (l+r)/2;
build(id*2, l, m);
build(id*2+1, m+1, r);
}
void push(ll id,ll l,ll r){
mn[id][0]+=lz[id];
mx[id][0]+=lz[id];
if(l!=r){
lz[id*2]+=lz[id];
lz[id*2+1]+=lz[id];
}
lz[id]=0;
}
void update(ll l, ll r, ll x){update(1,0,n-1,l,r, x);}
void update(ll id,ll l,ll r,ll i,ll j,ll x){
push(id,l,r);
if(l>j||r<i)return;
if(l>=i&&r<=j){
lz[id]+=x;
push(id,l,r);
return;
}
ll m=(l+r)/2;
update(id*2,l,m,i,j,x);
update(id*2+1,m+1,r,i,j,x);
mn[id]=min(mn[id*2],mn[id*2+1]);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
array<ll, 2> querymn(ll l, ll r){return querymn(1,0,n-1,l,r);}
array<ll, 2> querymn(ll id, ll l,ll r,ll i,ll j){
push(id,l,r);
if(l>j||r<i)return {INF, INF};
if(l>=i&&r<=j)return mn[id];
ll m=(l+r)/2;
return min(querymn(id*2,l,m,i,j),querymn(id*2+1,m+1,r,i,j));
}
array<ll, 2> querymx(ll l, ll r){return querymx(1,0,n-1,l,r);}
array<ll, 2> querymx(ll id, ll l,ll r,ll i,ll j){
push(id,l,r);
if(l>j||r<i)return {-INF, -INF};
if(l>=i&&r<=j)return mx[id];
ll m=(l+r)/2;
return max(querymx(id*2,l,m,i,j),querymx(id*2+1,m+1,r,i,j));
}
};
struct SegTree {
vll st;
ll n;
SegTree () {}
SegTree (ll n):n(n), st(4*n+4, INF) {}
void update(ll i, ll v){update(1,0,n-1,i,v);}
void update(ll id,ll l,ll r,ll i,ll v){
if(l==r)st[id] = v;
else{
ll m = (l+r)/2;
if(i<=m) update(id*2,l,m,i,v);
else update(id*2+1,m+1,r,i,v);
st[id] = min(st[id*2], st[id*2+1]);
}
}
// encontrar minimo indice tal que x>=a este
ll find (ll x) { return find (1, 0, n-1, x); }
ll find (ll id, ll l, ll r, ll x) {
if (st[id]>x) return INF;
if (l == r) return l;
ll m = (l+r)/2;
if (st[id*2] <= x) return find(id*2, l, m, x);
return find(id*2+1, m+1, r, x);
}
};
ll solve (int n, vector<int> a, ll sig) {
ll mx = *max_element(all(a));
vector<vll> ps(n+1);
fore (i, 1, n+1) ps[a[i]].pb(i);
SegTree st(n+2);
SegTreeLazy pf(n+2), g(n+2);
pf.build(1, 0, n+1);
g.build(1, 0, n+1);
ll ans = 1;
fore (i, 1, n+1) pf.update(i, n, +sig);
fo (i, n+2) st.update(i, INF);
for (ll x = 1; x <= mx; x++) {
if (ps[x].size() == 0) continue;
// cout << "Numero " << x << '\n';
for (ll i: ps[x]) {
pf.update(i, n, -sig);
g.update(i, n, +1);
}
// fore (i, 1, n+1) cout << pf.querymn(i, i)[0] << ' ';
// cout << '\n';
// fore (i, 1, n+1) cout << g.querymn(i, i)[0] << ' ';
// cout << '\n';
vector<array<ll, 2>> rd;
fo (_, ps[x].size()-1) {
rd.pb(pf.querymn(ps[x][_], ps[x][_+1]-1));
rd.pb(pf.querymx(ps[x][_], ps[x][_+1]-1));
}
rd.pb(pf.querymn(ps[x].back(), n));
rd.pb(pf.querymx(ps[x].back(), n));
rd.pb(pf.querymn(0, ps[x][0]-1));
rd.pb(pf.querymx(0, ps[x][0]-1));
// rd.pb({0, 0});
sort(all(rd));
for (auto [_, i]: rd) {
// cout << "Index " << i << '\n';
// cout << pf[i] << ' ' << g[i] << '\n';
/*
pf[i] >= pf[j]
sum=pf[i]-pf[j]
#0's=g[i]-g[j];
g[i]-pf[i]>=g[j]-pf[j]
*/
ll g_i = g.querymn(i, i)[0], pf_i = pf.querymn(i, i)[0];
auto p = st.find(g_i-pf_i);
if (p<i) {
ans = max(ans, g_i-g.querymn(p, p)[0]);
}
st.update(i, g_i-pf_i);
}
for (auto [_, i]: rd) {
st.update(i, INF);
}
for (ll i: ps[x]) {
pf.update(i, n, -sig);
g.update(i, n, -1);
}
}
return ans;
}
int sequence(int n, vector<int> a) {
{auto b = a;
a.clear();
a.pb(0);
for (ll x: b) a.pb(x);
a.pb(0);}
ll ans = solve(n, a, +1);
ans = max(ans, solve(n, a, -1));
return ans;
}
