#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct SegmentTree {
struct node {
int mn, h, d, delta;
node *left, *right;
node() : h(0), d(0), mn(0), delta(0), left(NULL), right(NULL) { };
void pull() {
mn = min(left->mn, right->mn);
}
void push(int l, int r) {
int m = l + r >> 1;
if (left == NULL) left = new node();
if (right == NULL) right = new node();
if (h != -1) {
left->h = h;
left->d = d;
right->h = h + (m - l + 1) * d;
right->d = d;
if (d > 0) {
left->mn = left->h;
right->mn = right->h;
} else {
left->mn = h + (m - l) * d;
right->mn = h + (r - l) * d;
}
h = -1;
delta = 0;
}
if (delta) {
left->mn += delta;
if (left->h != -1) left->h += delta;
else left->delta += delta;
right->mn += delta;
if (right->h != -1) right->h += delta;
else right->delta += delta;
delta = 0;
}
}
} *root;
int n;
void upd(node* &v, int l, int r, int ql, int qr, int h, int d) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
v->delta = 0;
v->h = h + (l - ql + 1) * d, v->d = d;
v->mn = d > 0 ? v->h : v->h + (r - l) * d;
return;
}
v->push(l, r);
int m = l + r >> 1;
upd(v->left, l, m, ql, qr, h, d);
upd(v->right, m + 1, r, ql, qr, h, d);
v->pull();
}
void upd2(node* &v, int l, int r, int ql, int qr, int delta) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
v->mn += delta;
if (v->h != -1) v->h += delta;
else v->delta += delta;
return;
}
v->push(l, r);
int m = l + r >> 1;
upd2(v->left, l, m, ql, qr, delta);
upd2(v->right, m + 1, r, ql, qr, delta);
v->pull();
}
int find_first(node* &v, int l, int r, int h) {
if (l == r) return l;
v->push(l, r);
int m = l + r >> 1;
if (v->left->mn < h) return find_first(v->left, l, m, h);
return find_first(v->right, m + 1, r, h);
}
int qry(node* &v, int l, int r, int u) {
if (l == r) return v->mn;
v->push(l, r);
int m = l + r >> 1;
if (u <= m) return qry(v->left, l, m, u);
return qry(v->right, m + 1, r, u);
}
SegmentTree() : root(NULL) { };
SegmentTree(int n_) : root(new node()), n(n_) { }; // Declares an array of size n with initial elements zero, zero-based indexing.
int qry(int u) { // Returns the element at index u.
if (u < 0 || u > n - 1) return 0;
return qry(root, 0, n - 1, u);
}
int find_first(int h) { // Returns the index of the first element < h in the array, or -1 if no such element exists.
if (root->mn >= h) return -1;
return find_first(root, 0, n - 1, h);
}
void upd(int l, int r, int h, int d) { // Assigns an arithmetic progression h + id to elements in range [l, r], i = 1, 2, 3, ..., r - l + 1.
if (l > r) return;
upd(root, 0, n - 1, l, r, h, d);
}
void upd2(int l, int r, int delta) { // Adds delta to elements in range [l, r].
if (l > r) return;
upd2(root, 0, n - 1, l, r, delta);
}
} s[500000], pre[500000];
int sequence(int n, vector<int> a) {
int ans = 0;
if (n <= 3e3) {
oset<pair<int, int>> s;
vector<int> f(n + 1);
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
s.insert({a[j], j});
++f[a[j]];
int med1 = (*s.find_by_order((j - i) / 2)).first, med2 = (*s.find_by_order((j - i + 1) / 2)).first;
ans = max(ans, max(f[med1], f[med2]));
}
s.clear();
f = vector<int> (n + 1);
}
return ans;
} else {
for (int i = 0; i < n; i++) s[i] = SegmentTree(n), pre[i] = SegmentTree(n);
for (int i = 0; i < n; i++) s[i].upd(0, n - 1, 1, -1);
for (int i = 0; i < n; i++) {
--a[i];
pre[a[i]].upd2(i, n - 1, 1);
s[a[i]].upd(i, i, 2 * pre[a[i]].qry(i - 1) - i + 1, -1);
s[a[i]].upd(i + 1, n - 1, 2 * pre[a[i]].qry(i) - i, -1);
}
for (int i = 0; i < n; i++) {
int l = s[a[i]].find_first(2 * pre[a[i]].qry(i) - i);
if (l == -1 || l > i) continue;
ans = max(ans, pre[a[i]].qry(i) - pre[a[i]].qry(l - 1));
}
sort(a.begin(), a.end());
return max(ans, (a[n >> 1] == 1 || a[(n - 1) >> 1] == 1 ? pre[1].qry(n - 1) : 0));
}
}
