#include "sequence.h"
#include "bits/stdc++.h"
using namespace std;
template<typename T> struct SegTree {
vector<T> tree;
int size;
T neutral_element = 1e9; // sum - 0, mx - (-INF), mn - INF
inline T merge(T a, T b) {
return min(a, b);
}
void init(int n) {
size = 1;
while (size <= n) size *= 2;
tree.assign(2 * size, neutral_element);
}
void build(vector<T> &a) {
size = 1;
while (size < a.size()) size *= 2;
tree.assign(2 * size, neutral_element);
for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
for (int i = size - 1; i > 0; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
}
void upd(int p, T value) { // upd value at position p
p += size;
tree[p] = merge(value, tree[p]);
for (; p > 1; p >>= 1) tree[p >> 1] = merge(tree[p], tree[p ^ 1]);
}
T get(int l, int r) { // sum on interval [l, r]
if (l > r) return neutral_element;
T res = neutral_element;
for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = merge(res, tree[l++]);
if (r & 1) res = merge(res, tree[--r]);
}
return res;
}
};
template<typename T> struct Fenwick {
int n;
vector<T> tree;
void init(int len) {
n = len;
tree.assign(n + 1, 0);
}
void update(int i, T v) {
for (i++; i <= n; i += i & (-i)) tree[i] += v;
}
T get(int i) {
T sum = 0;
for (i++; i > 0; i -= i & (-i)) sum += tree[i];
return sum;
}
T get(int l, int r) {
return get(r) - get(l - 1);
}
};
int sequence(int n, vector<int> a) {
int ans = 1;
for (int l = 0; l < n; l++) {
Fenwick<int> fw; fw.init(n + 1);
fw.update(a[l], 1);
set<int> st; st.insert(a[l]);
int mid = a[l], ln = 1;
for (int r = l + 1; r < n; r++) {
ln++;
fw.update(a[r], 1);
st.insert(a[r]);
auto it = st.lower_bound(mid);
for (int j = 0; j < 3 and it != st.begin(); j++, it--);
for (int j = 0; j < 6 and it != st.end(); j++, it++) {
int prev = fw.get(*it - 1);
int now = fw.get(*it);
if (prev > (ln + 1) / 2) continue;
if (now >= (ln + 1) / 2) {
// cout << l << ' ' << r << ' ' << *it << ' ' << now - prev << endl;
ans = max(ans, now - prev);
mid = *it;
}
}
}
}
return ans;
}
