#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
#include "sequence.h"
using namespace std;
mt19937 rnd(7069);
typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;
using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
const int MAX = int(2e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const int max_N = 500005;
vi g[max_N];
pii pref[max_N * 4], suf[max_N * 4], lazy[max_N * 4];
int a[max_N];
int n, ans = 1;
void merge(int pos) {
pref[pos].ff = min(pref[2 * pos].ff, pref[2 * pos + 1].ff);
pref[pos].ss = max(pref[2 * pos].ss, pref[2 * pos + 1].ss);
suf[pos].ff = min(suf[2 * pos].ff, suf[2 * pos + 1].ff);
suf[pos].ss = max(suf[2 * pos].ss, suf[2 * pos + 1].ss);
}
void push(int pos) {
pref[2 * pos].ff += lazy[pos].ff;
pref[2 * pos].ss += lazy[pos].ff;
pref[2 * pos + 1].ff += lazy[pos].ff;
pref[2 * pos + 1].ss += lazy[pos].ff;
suf[2 * pos].ff += lazy[pos].ss;
suf[2 * pos].ss += lazy[pos].ss;
suf[2 * pos + 1].ff += lazy[pos].ss;
suf[2 * pos + 1].ss += lazy[pos].ss;
lazy[2 * pos].ff += lazy[pos].ff;
lazy[2 * pos + 1].ff += lazy[pos].ff;
lazy[2 * pos].ss += lazy[pos].ss;
lazy[2 * pos + 1].ss += lazy[pos].ss;
lazy[pos] = { 0,0 };
}
void bld(int l = 1, int r = n, int pos = 1) {
if (l == r) {
pref[pos] = { l,l };
suf[pos] = { n - l + 1, n - l + 1 };
return;
}
int mid = (l + r) / 2;
bld(l, mid, 2 * pos);
bld(mid + 1, r, 2 * pos + 1);
merge(pos);
}
void upd_pref(int l, int r, int val, int tl = 1, int tr = n, int pos = 1) {
if (l == tl && r == tr) {
lazy[pos].ff += val;
pref[pos].ff += val;
pref[pos].ss += val;
return;
}
push(pos);
int mid = (tl + tr) / 2;
if (mid >= r) {
upd_pref(l, r, val, tl, mid, 2 * pos);
}
else if (mid < l) {
upd_pref(l, r, val, mid + 1, tr, 2 * pos + 1);
}
else {
upd_pref(l, mid, val, tl, mid, 2 * pos);
upd_pref(mid + 1, r, val, mid + 1, tr, 2 * pos + 1);
}
merge(pos);
}
void upd_suf(int l, int r, int val, int tl = 1, int tr = n, int pos = 1) {
if (l == tl && r == tr) {
lazy[pos].ss += val;
suf[pos].ff += val;
suf[pos].ss += val;
return;
}
push(pos);
int mid = (tl + tr) / 2;
if (mid >= r) {
upd_suf(l, r, val, tl, mid, 2 * pos);
}
else if (mid < l) {
upd_suf(l, r, val, mid + 1, tr, 2 * pos + 1);
}
else {
upd_suf(l, mid, val, tl, mid, 2 * pos);
upd_suf(mid + 1, r, val, mid + 1, tr, 2 * pos + 1);
}
merge(pos);
}
pii qry(int l, int r, int type, int tl = 1, int tr = n, int pos = 1) {
if (l <= 0 || l > r) return { 0,0 };
if (l == tl && r == tr) {
return (type == 1 ? pref[pos] : suf[pos]);
}
push(pos);
int mid = (tl + tr) / 2;
if (mid >= r) {
return qry(l, r, type, tl, mid, 2 * pos);
}
if (mid < l) {
return qry(l, r, type, mid + 1, tr, 2 * pos + 1);
}
pii opt1 = qry(l, mid, type, tl, mid, 2 * pos);
pii opt2 = qry(mid + 1, r, type, mid + 1, tr, 2 * pos + 1);
return { min(opt1.ff,opt2.ff),max(opt1.ss,opt2.ss) };
}
int sequence(int N, std::vector<int> A) {
n = N;
for (int i = 1; i <= n; ++i) {
a[i] = A[i - 1];
g[a[i]].pub(i);
}
bld();
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < (int)g[i].size(); ++j) {
upd_pref(g[i][j], n, -1);
upd_suf(1, g[i][j], -1);
}
for (int k1 = 0; k1 < (int)g[i].size(); ++k1) {
int cnt = 1;
for (int k2 = k1 + 1; k2 < (int)g[i].size(); ++k2) {
++cnt;
int l = g[i][k1], r = g[i][k2];
int val = qry(r, r, 1).ff - qry(l - 1, l - 1, 1).ff;
int dif;
if (val > cnt) {
dif = qry(1, l, 2).ff - qry(l, l, 2).ff + qry(r, n, 1).ff - qry(r, r, 1).ff;
if (val + dif <= cnt) {
ans = max(ans, cnt);
}
}
else if (val < -cnt) {
dif = qry(1, l, 2).ss - qry(l, l, 2).ss + qry(r, n, 1).ss - qry(r, r, 1).ss;
if (val + dif >= -cnt) {
ans = max(ans, cnt);
}
}
else {
ans = max(ans, cnt);
}
}
}
for (int j = 0; j < (int)g[i].size(); ++j) {
upd_pref(g[i][j], n, -1);
upd_suf(1, g[i][j], -1);
}
}
return ans;
}
/*
9
1 1 2 3 4 3 2 1 1
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/
