#include "sequence.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
struct dt
{
ll mn = INT_MAX, mx = INT_MIN;
dt(){}
};
const ll mx = 1e6;
vector<ll>pref(mx, 0);
dt st[4*mx];
vector<ll>lazy(4*mx, 0);
dt merge(dt a, dt b)
{
dt ret;
ret.mx = max(a.mx, b.mx);
ret.mn = min(a.mn, b.mn);
return ret;
}
void build(ll l, ll r, ll v)
{
if (l==r)
{
st[v].mx = st[v].mn = pref[l];
return;
}
ll mid = (l+r)/2;
build(l,mid,2*v);
build(mid+1, r, 2*v+1);
st[v] = merge(st[2*v],st[2*v+1]);
}
void push(ll l, ll r, ll v)
{
if (lazy[v]==0) return;
st[v].mn += lazy[v];
st[v].mx += lazy[v];
if (l!=r)
{
lazy[2*v] += lazy[v];
lazy[2*v+1] += lazy[v];
}
lazy[v] = 0;
}
dt getans(ll l, ll r, ll v, ll ql, ll qr)
{
push(l, r, v);
if (r<ql or l>qr)
return dt();
if (l>=ql and r<=qr)
return st[v];
ll mid = (l+r)/2;
return merge(getans(l, mid, 2*v, ql, qr), getans(mid+1, r, 2*v+1, ql, qr));
}
void update(ll l, ll r, ll v, ll ql, ll qr, ll val)
{
push(l, r, v);
if (r<ql or l>qr)
return;
if (l>=ql and r<=qr)
{
lazy[v] += val;
push(l, r, v);
return;
}
ll mid = (l+r)/2;
update(l, mid, 2*v, ql, qr, val);
update(mid+1, r, 2*v+1, ql, qr, val);
st[v] = merge(st[2*v], st[2*v+1]);
}
int sequence(int N, std::vector<int> A) {
ll n = N;
vector<ll>v;
v.push_back(0);
for (int i=0 ; i<n ; i++)
v.push_back(A[i]);
for (int i=1 ; i<=n ;i ++)
pref[i] = pref[i-1]+1;
build(1, n, 1);
vector<vector<ll>>g(n+1);
for (int i=1 ; i<=n ;i++)
g[v[i]].push_back(i);
ll res = 1;
for (int i=1 ; i<=n ; i++)
{
if (g[i].empty()) continue;
ll m = g[i].size();
vector<ll>l1(m+1), r1(m+1);
for (int j=0 ; j<m ; j++)
{
l1[j] = (g[i][j]!=1)? getans(1, n, 1, 1, g[i][j]-1).mn : 0;
r1[j] = getans(1, n, 1, g[i][j], n).mx;
}
for (int j=0 ; j<g[i].size() ; j++)
update(1, n, 1, g[i][j], n, -2);
vector<ll>l2(m+1), r2(m+1);
for (int j=0 ; j<m ; j++)
{
l2[j] = ((g[i][j]!=1)? getans(1, n, 1, 1, g[i][j]-1).mx : 0);
r2[j] = getans(1, n, 1, g[i][j], n).mn;
}
ll l = 0, r = 0;
while (r<m)
{
while (r<m and r1[r]-l1[l]>=0 and r2[r]-l2[l]<=0)
{
r++;
// cout<<l<<" "<<r<<endl;
res = max(res, r-l);
}
l++;
r = max(r, l);
}
}
return res;
}
/*
9
1 1 2 3 4 3 2 1 1
7
1 2 3 1 2 1 3
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/
