#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=5e5+5;
int n, l, r, ans=1;
vector<int> p[nx];
struct segtree
{
struct node
{
int sm, mxp, mnp;
node(int sm=0, int mxp=0, int mnp=0): sm(sm), mxp(mxp), mnp(mnp) {}
friend node operator+ (const node &lhs, const node &rhs) {
return node(lhs.sm+rhs.sm, max(lhs.mxp, lhs.sm+rhs.mxp), min(lhs.mnp, lhs.sm+rhs.mnp));
}
} d[4*nx];
void build(int l, int r, int i)
{
if (l==r) return d[i]=node(l!=0, l!=0, l!=0), void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=d[2*i]+d[2*i+1];
}
void update(int l, int r, int i, int idx, int vl)
{
if (l==r) return d[i]=node(vl, vl, vl), void();
int md=(l+r)/2;
if (idx<=md) update(l, md, 2*i, idx, vl);
else update(md+1, r, 2*i+1, idx, vl);
d[i]=d[2*i]+d[2*i+1];
}
node query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return node(0, 0, 0);
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return query(l, md, 2*i, ql ,qr)+query(md+1, r, 2*i+1, ql, qr);
}
} smx, smn;
int sequence(int N, std::vector<int> A) {
n=N;
for (int i=0; i<n; i++) p[A[i]].push_back(i+1);
smx.build(0, n, 1);
smn.build(0, n, 1);
for (int i=1; i<=n; i++)
{
for (auto idx:p[i]) smn.update(0, n, 1, idx, -1);
for (int j=0; j<p[i].size(); j++)
{
while (j+ans+1-1<p[i].size())
{
int l=p[i][j], r=p[i][j+ans];
int mxp=smx.query(0, n, 1, r, n).mxp+smx.query(0, n, 1, 0, r-1).sm-smx.query(0, n, 1, 0, l-1).mnp;
int mnp=smn.query(0, n, 1, r, n).mnp+smn.query(0, n, 1, 0, r-1).sm-smn.query(0, n, 1, 0, l-1).mxp;
if (mxp>=0&&mnp<=0) ans++;
else break;
}
}
for (auto idx:p[i]) smx.update(0, n, 1, idx, -1);
}
return ans;
}
