#include "sequence.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair
#define F first
#define all(v) v.begin(),v.end()
#define V vector
#define pb push_back
#define S second
const ll MOD=(ll)1e9+7;
void file() {
freopen("input.txt.txt", "r", stdin);
freopen("output.txt.txt", "w", stdout);
}
struct segtree {
private:
struct node {
ll sum;
};
node neutral = {0};
node single(int x) {
return {x};
}
node merge(node a, node b) {
return {a.sum + b.sum};
};
public:
int size;
V<node> query;
void init(int n) {
size = 1;
while (size < n)size *= 2;
query.assign(2 * size, neutral);
}
void build(V<int> &a, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < a.size())
query[x] = single(a[lx]);
return;
}
int m = (lx + rx) / 2;
build(a, 2 * x + 1, lx, m);
build(a, 2 * x + 2, m, rx);
query[x] = merge(query[2 * x + 1], query[2 * x + 2]);
}
void build(V<int> a) {
build(a, 0, 0, size);
}
void set(int i, int v, int x, int lx, int rx) {
if (rx - lx == 1) {
query[x] = single(v);
return;
}
int m = (lx + rx) / 2;
if (i < m) {
set(i, v, 2 * x + 1, lx, m);
} else
set(i, v, 2 * x + 2, m, rx);
query[x] = merge(query[2 * x + 1], query[2 * x + 2]);
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
node calc(int l, int r, int x, int lx, int rx) {
if (l <= lx && rx <= r)
return query[x];
if (lx >= r || rx <= l)
return neutral;
int m = (lx + rx) / 2;
node a = calc(l, r, 2 * x + 1, lx, m);
node b = calc(l, r, 2 * x + 2, m, rx);
return merge(a, b);
}
ll calc(int l, int r) {
return calc(l, r, 0, 0, size).sum;
}
};
int sequence(int N, std::vector<int> A) {
int ans = 0;
segtree tree;
for (int i = 0; i < N; i++) {
tree.init(N + 1);
V<int> occ(N + 1, 0);
tree.build(occ);
for (int j = i; j < N; j++) {
int d = j - i + 1;
occ[A[j]]++;
tree.set(A[j], occ[A[j]]);
int md1 = -1, md2 = -1;
int l = 1, r = N;
while (l <= r) {
int m = l + (r - l) / 2;
if (tree.calc(1, m + 1) >= (d + 1) / 2) {
md1 = m;
r = m - 1;
} else
l = m + 1;
}
l = 1, r = N;
while (l <= r) {
int m = l + (r - l) / 2;
if (tree.calc(1, m + 1) >= (d + 2) / 2) {
md2 = m;
r = m - 1;
} else
l = m + 1;
}
ans = max(ans, max(occ[md1], occ[md2]));
}
}
return ans;
}
