/*#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")*/
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
//using namespace __gnu_pbds;
const ll INF = 1e18+7;
const int lg = 20;
//const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
mt19937 rng(1488);
ll randll(ll l, ll r) {
return uniform_int_distribution<ll>(l, r)(rng);
}
struct ed {
ll pref, suff, sum;
};
vector<ed> tree;
void bt(ll v, ll tl, ll tr) {
if (tl == tr) {
tree[v] = {0, 0, -1};
return;
}
ll tm = (tl+tr)/2;
bt(v*2, tl, tm);
bt(v*2+1, tm+1, tr);
tree[v].pref = max(tree[v*2].pref, tree[v*2].sum+tree[v*2+1].pref);
tree[v].suff = max(tree[v*2+1].suff, tree[v*2+1].sum+tree[v*2].suff);
tree[v].sum = tree[v*2+1].sum + tree[v*2].sum;
}
void upd(ll idx, ll val, ll v, ll tl, ll tr) {
if (tl == tr) {
tree[v] = {max((ll)0, val), max((ll)0, val), val};
return;
}
ll tm = (tl+tr)/2;
if (idx <= tm) upd(idx, val, v*2, tl, tm);
else upd(idx, val, v*2+1, tm+1, tr);
tree[v].pref = max(tree[v*2].pref, tree[v*2].sum+tree[v*2+1].pref);
tree[v].suff = max(tree[v*2+1].suff, tree[v*2+1].sum+tree[v*2].suff);
tree[v].sum = tree[v*2+1].sum + tree[v*2].sum;
}
ed get(ll l, ll r, ll v, ll tl, ll tr) {
//cout << "! " << tl << ' ' << tr << endl;
if (l <= tl && tr <= r) {
return tree[v];
}
if (tl > r || tr < l) return {0, 0, 0};
ll tm = (tl+tr)/2;
ed p = get(l, r, v*2, tl, tm), p1 = get(l, r, v*2+1, tm+1, tr), res;
res.pref = max(p.pref, p.sum+p1.pref);
res.suff = max(p1.suff, p1.sum+p.suff);
res.sum = p1.sum + p.sum;
return res;
}
vll tree1;
ll get_min(ll l, ll r, ll v, ll tl, ll tr) {
if (l <= tl && tr <= r) return tree1[v];
if (tl > r || tr < l) return INF;
ll tm = (tl+tr)/2;
//push(v, tl, tr);
ll p = get_min(l, r, v*2, tl, tm), p1 = get_min(l, r, v*2+1, tm+1, tr);
return min(p,p1);
}
void update(ll idx, ll val, ll v, ll tl, ll tr) {
if (tl == tr) {
if (val == INF) tree1[v] = val;
else tree1[v] = min(tree1[v], val);
return;
}
ll tm = (tl+tr)/2;
if (idx <= tm)update(idx, val, v*2, tl, tm);
else update(idx, val, v*2+1, tm+1, tr);
tree1[v] = min(tree1[v*2], tree1[v*2+1]);
}
int sequence(int n, vi a) {
tree.clear();
tree.resize(n*4+7);
tree1.clear();
tree1.resize(n*8+7, INF);
vvll v(n+7);
for (int i = 0; i < n; i ++) {
v[a[i]].pb(i);
}
bt(1, 0, n-1);
ll maxl = 0;
for (int i = 1; i <= n; i ++) {
for (int j : v[i]) {
upd(j, 1, 1, 0, n-1);
}
ll last = -1, k = 0;
vll v1;
for (int j : v[i]) {
//cout << last+1 << ' ' << j << endl;
ed p = get(last+1, j, 1, 0, n-1);
ll pref = get(0, j, 1, 0, n-1).sum;
update(pref - p.suff + n, k, 1, 0, n*2);
v1.pb(pref - p.suff + n);
//cout << pref - p.suff << ' ' << pref << ' ';
ll x = n-1;
if (k+1 < v[i].size()) x = v[i][k+1]-1;
ll p1 = get(j, x, 1, 0, n-1).pref-1;
//cout << p1 << endl;
ll res = k-get_min(0, pref+p1+n, 1, 0, 2*n)+1;
//cout << k << ' ' << get_min(0, pref+p1+n, 1, 0, 2*n) << endl;
//cout << endl;
maxl = max(maxl, res);
last = j;
k ++;
}
for (int j : v1) {
update(j, INF, 1, 0, n*2);
}
}
return maxl;
}
/*int main() {
speed;
srand(time(0));
cout << sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2});
}*/
