#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 {
vll mn, mx, lz;
ll n;
SegTreeLazy () { }
SegTreeLazy (ll n): n(n), mn(4*n+4, 0), mx(4*n+4, 0), lz(4*n+4, 0) { }
void push(ll id,ll l,ll r) {
if (lz[id] == 0) return;
mn[id]+=lz[id];
mx[id]+=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]);
}
ll querymn(ll l, ll r){return querymn(1,0,n-1,l,r);}
ll querymn(ll id, ll l,ll r,ll i,ll j){
push(id,l,r);
if(l>j||r<i)return 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));
}
ll querymx(ll l, ll r){return querymx(1,0,n-1,l,r);}
ll querymx(ll id, ll l,ll r,ll i,ll j){
push(id,l,r);
if(l>j||r<i)return -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));
}
};
ll solve (int n, vector<int> a) {
ll mx = *max_element(all(a));
vector<vll> ps(n+1);
fore (i, 1, n+1) ps[a[i]].pb(i);
SegTreeLazy st1(n+1), st2(n+1);
ll ans = 1;
fore (i, 1, n+1) {
st1.update(i, n, +1);
st2.update(i, n, +1);
}
for (ll x = 1; x <= mx; x++) {
if (ps[x].size() == 0) continue;
for (ll i: ps[x]) {
st1.update(i, n, -2);
}
ll r = 0;
fo (l, ps[x].size()) {
while (r<ps[x].size()) {
/*
[i, j]
*/
ll mn = st1.querymn(ps[x][r], n);
ll mx = st1.querymx(0, ps[x][l]-1);
ll chiquibai = mn-mx;
mx = st2.querymx(ps[x][r], n);
mn = st2.querymn(0, ps[x][l]-1);
ll chiquibai2 = mx-mn;
if (chiquibai*chiquibai2 > 0) break;
++r;
}
ans = max(ans, r-l);
}
for (ll i: ps[x]) {
st2.update(i, n, -2);
}
}
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);
return ans;
}
