#include "sequence.h"
#include <iostream>
#include <vector>
#define int long long
using namespace std;
int n, a[500010], maxx, node[2000010][2][2], lz[2000010][2][2]; // 0: updated, 1: not updated; 0: max, 1: min
vector<int> pos[500010];
void build(int id, int x, int y) {
if (x == y) {
node[id][0][0] = node[id][0][1] = node[id][1][1] = node[id][1][0] = x;
return;
}
int mid = (x+y)/2;
build(id*2,x,mid);
build(id*2+1,mid+1,y);
node[id][0][0] = max(node[id*2][0][0],node[id*2+1][0][0]);
node[id][1][0] = max(node[id*2][1][0],node[id*2+1][1][0]);
node[id][0][1] = min(node[id*2][0][1],node[id*2+1][0][1]);
node[id][1][1] = min(node[id*2][1][1],node[id*2+1][1][1]);
}
void update(int i, int j, int id, int x, int y, int l, int r) {
if ((l <= x) && (y <= r)) {
node[id][i][j] -= 2;
lz[id][i][j] -= 2;
return;
}
if ((y < l) || (r < x)) return;
int mid = (x+y)/2;
node[id*2][i][j] += lz[id][i][j];
node[id*2+1][i][j] += lz[id][i][j];
lz[id*2][i][j] += lz[id][i][j];
lz[id*2+1][i][j] += lz[id][i][j];
lz[id][i][j] = 0;
update(i,j,id*2,x,mid,l,r);
update(i,j,id*2+1,mid+1,y,l,r);
if (!j) node[id][i][j] = max(node[id*2][i][j],node[id*2+1][i][j]);
else node[id][i][j] = min(node[id*2][i][j],node[id*2+1][i][j]);
}
int query(int i, int j, int id, int x, int y, int l, int r) {
if ((l <= x) && (y <= r)) return node[id][i][j];
if ((y < l) || (r < x)) {
if (!j) return -1e9;
else return 1e9;
}
int mid = (x+y)/2;
node[id*2][i][j] += lz[id][i][j];
node[id*2+1][i][j] += lz[id][i][j];
lz[id*2][i][j] += lz[id][i][j];
lz[id*2+1][i][j] += lz[id][i][j];
lz[id][i][j] = 0;
if (!j) return max(query(i,j,id*2,x,mid,l,r),query(i,j,id*2+1,mid+1,y,l,r));
else return min(query(i,j,id*2,x,mid,l,r),query(i,j,id*2+1,mid+1,y,l,r));
}
signed sequence(signed N, std::vector<signed> A) {
n = N;
for (int i = 1; i <= n; i++) {
a[i] = A[i-1];
pos[a[i]].push_back(i);
}
build(1,0,n);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < pos[i].size(); j++) {
update(0,0,1,0,n,pos[i][j],n);
update(0,1,1,0,n,pos[i][j],n);
}
int l = 0, r = 0;
while (r < pos[i].size()) {
if ((query(1,0,1,0,n,pos[i][r],n)-query(1,1,1,0,n,0,pos[i][l]-1))*(query(0,1,1,0,n,pos[i][r],n)-query(0,0,1,0,n,0,pos[i][l]-1)) <= 0) r++;
else l++;
maxx = max(maxx,r-l);
}
for (int j = 0; j < pos[i].size(); j++) {
update(1,0,1,0,n,pos[i][j],n);
update(1,1,1,0,n,pos[i][j],n);
}
}
return maxx;
}
