#include <bits/stdc++.h>
using namespace std;
const int N = 510000;
struct segtree {
vector<int> vmn, vmx, lz;
segtree() {}
segtree(int n) {
vmn = vmx = lz = vector<int>(4 * n + 1, 0);
}
void push(int v, int l, int r) {
if (lz[v] == 0) return;
vmn[v] += lz[v];
vmx[v] += lz[v];
if (l != r) {
lz[v * 2 + 0] += lz[v];
lz[v * 2 + 1] += lz[v];
}
lz[v] = 0;
}
void upd(int v, int l, int r, int ql, int qr, int x) {
push(v, l, r);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
lz[v] += x;
push(v, l, r);
return;
}
int mid = (l + r) / 2;
upd(v * 2 + 0, l, mid, ql, qr, x);
upd(v * 2 + 1, mid + 1, r, ql, qr, x);
vmn[v] = min(vmn[v * 2 + 0], vmn[v * 2 + 1]);
vmx[v] = max(vmx[v * 2 + 0], vmx[v * 2 + 1]);
}
int getmin(int v, int l, int r, int ql, int qr) {
push(v, l, r);
if (qr < l || r < ql) return (int)(1e18);
if (ql <= l && r <= qr) return vmn[v];
int mid = (l + r) / 2;
return min(getmin(v * 2 + 0, l, mid, ql, qr), getmin(v * 2 + 1, mid + 1, r, ql, qr));
}
int getmax(int v, int l, int r, int ql, int qr) {
push(v, l, r);
if (qr < l || r < ql) return (int)(-1e18);
if (ql <= l && r <= qr) return vmx[v];
int mid = (l + r) / 2;
return max(getmax(v * 2 + 0, l, mid, ql, qr), getmax(v * 2 + 1, mid + 1, r, ql, qr));
}
};
vector<int> pos[N];
int sequence(int n, vector<int> a) {
vector<int> vals = a;
sort(begin(vals), end(vals));
int m1 = vals[(n - 1) / 2];
int m2 = vals[n - 1 - (n - 1) / 2];
int cnt_m1 = 0, cnt_m2 = 0;
for (int x : a)
if (x == m1) cnt_m1++;
else if (x == m2) cnt_m2++;
int ans = max(cnt_m1, cnt_m2);
for (int i = 0; i < n; i++)
pos[a[i]].push_back(i + 1);
segtree seg;
seg = segtree(n + 1);
for (int i = 1; i <= n; i++)
seg.upd(1, 0, n, i, n, 1);
for (int i = 1; i < m1; i++) {
for (int j : pos[i])
seg.upd(1, 0, n, j, n, -2);
int m = (int) pos[i].size();
vector<int> pmax(m), pmin(m);
for (int j = 0; j < m; j++) {
pmax[j] = seg.getmax(1, 0, n, 0, pos[i][j] - 1);
pmin[j] = seg.getmin(1, 0, n, pos[i][j], n);
}
for (int j = 0; j < m; j++)
ans = max(ans, (int) (upper_bound(begin(pmin), end(pmin), pmax[j]) - begin(pmin) - j));
}
seg = segtree(n + 1);
for (int i = 1; i <= n; i++)
seg.upd(1, 0, n, i, n, -1);
for (int i = n; i > m2; i--) {
for (int j : pos[i])
seg.upd(1, 0, n, j, n, 2);
int m = (int) pos[i].size();
vector<int> pmax(m), pmin(m);
for (int j = 0; j < m; j++) {
pmax[j] = -seg.getmin(1, 0, n, 0, pos[i][j] - 1);
pmin[j] = -seg.getmax(1, 0, n, pos[i][j], n);
}
for (int j = 0; j < m; j++)
ans = max(ans, (int) (upper_bound(begin(pmin), end(pmin), pmax[j]) - begin(pmin) - j));
}
return ans;
}
