#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=5e5+5;
int n, l, r;
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);
}
} s;
int sequence(int N, std::vector<int> A) {
l=1, r=N;
n=N;
for (int i=0; i<n; i++) p[A[i]].push_back(i+1);
while (l<r)
{
int md=(l+r+1)/2, can=0;
s.build(0, n, 1);
for (int i=1; i<=n; i++)
{
vector<int> mn(p[i].size()), mx(p[i].size());
for (int j=0; j+md-1<p[i].size(); j++) mx[j]=s.query(0, n, 1, p[i][j+md-1], n).mxp+s.query(0, n, 1, 0, p[i][j+md-1]-1).sm-s.query(0, n, 1, 0, p[i][j]-1).mnp;
for (int j=0; j<p[i].size(); j++) s.update(0, n, 1, p[i][j], -1);
for (int j=0; j+md-1<p[i].size(); j++)
{
mn[j]=s.query(0, n, 1, p[i][j+md-1], n).mnp+s.query(0, n, 1, 0, p[i][j+md-1]-1).sm-s.query(0, n, 1, 0, p[i][j]-1).mxp;
if (mx[j]>=0&&mn[j]<=0) can=1;
}
if (can) break;
}
if (can) l=md;
else r=md-1;
}
return l;
}
