#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 Fenwick {
vll ft;
ll n;
Fenwick () { }
Fenwick (ll n): n(n+2), ft (n+4, 0) { }
void update (ll i, ll v) {
i++;
for (; i <= n; i += lsb(i))
ft[i] += v;
}
ll query (ll i) {
i++;
ll r = 0;
for (; i > 0; i -= lsb(i))
r += ft[i];
return r;
}
void update (ll l, ll r, ll v) { update(l, +v); update(r+1, -v); }
ll query (ll l, ll r) { if (l>r) return 0ll; return query(r) - query(l-1); }
};
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]);
}
}
ll query(ll l,ll r){return query(1,0,n-1,l,r);}
ll query(ll id,ll l,ll r,ll i,ll j){
if(l>j || r<i)return INF;
if(l>=i && r<=j)return st[id];
ll m = (l+r)/2;
return min(query(id*2,l,m,i,j), query(id*2+1,m+1,r,i,j));
}
// 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 mx = *max_element(all(a));
SegTree st(n+2);
Fenwick ft(n+2);
ll ans = 1;
for (ll x = 1; x <= mx; x++) {
vll p, c(n+2, 0ll), pf(n+2, 0ll), g(n+2, 0ll);
vector<array<ll, 2>> rd;
fore (i, 1, n+1) {
if (a[i] == x) p.pb(i);
else if (a[i] < x) c[i] = -1;
else c[i] = +1;
pf[i] = pf[i-1] + c[i];
g[i] = g[i-1] + (c[i] == 0 ? 1 : 0);
rd.pb({pf[i], i});
}
rd.pb({0, 0});
sort(all(rd));
fo (i, n+1) st.update(i, INF);
for (auto [_, i]: rd) {
/*
pf[i] >= pf[j]
sum=pf[i]-pf[j]
#0's=g[i]-g[j];
g[i]-pf[i]>=g[j]-pf[j]
*/
auto p = st.find(g[i]-pf[i]);
if (p<i) {
ans = max(ans, g[i]-g[p]);
}
st.update(i, g[i]-pf[i]);
}
}
return ans;
}
int sequence(int n, vector<int> a) {
ll mx = *max_element(all(a));
{auto b = a;
a.clear();
a.pb(0);
for (ll x: b) a.pb(x);
a.pb(0);}
ll ans = solve(n, a);
reverse(all(a));
ans = max(ans, solve(n, a));
return ans;
}
