#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update
>;
#define vec vector
#define all(x) (x).begin(), (x).end()
int sequence(int N, std::vector<int> A) {
if (N <= 2000) {
int ans = 0;
for(int i = 0; i < N; i++) {
auto tree = ordered_set<pair<int,int>>();
map<int,int> f;
for(int j = i; j < N; j++) {
tree.insert({A[j], j});
f[A[j]]++;
if (tree.size() % 2 == 0) {
int a = tree.find_by_order(tree.size() / 2 - 1)->first;
int b = tree.find_by_order(tree.size() / 2)->first;
ans = max(ans, f[a]);
ans = max(ans, f[b]);
} else {
int a = tree.find_by_order(tree.size() / 2)->first;
ans = max(ans, f[a]);
}
}
}
return ans;
}
int ans = 0;
int i = max_element(all(A)) - A.begin();
int l = i, r = i;
ordered_set<pair<int,int>> tree;
map<int,int> f;
while (l > 0 || r < N - 1) {
bool right = 0, left = 0;
if (l == 0) right = 1;
else if (r == N - 1) left = 1;
else if (A[l - 1] > A[r + 1]) left = 1;
else right = 1;
if (right) {
r++;
tree.insert({A[r], r});
f[A[r]]++;
} else if (left) {
l--;
tree.insert({A[l], l});
f[A[l]]++;
}
if (tree.size() % 2 == 0) {
int a = tree.find_by_order(tree.size() / 2 - 1)->first;
int b = tree.find_by_order(tree.size() / 2)->first;
ans = max(ans, f[a]);
ans = max(ans, f[b]);
} else {
int a = tree.find_by_order(tree.size() / 2)->first;
ans = max(ans, f[a]);
}
}
f.clear();
for (int j = 0; j < N; j++) {
if (j == i) f.clear();
f[A[j]]++;
ans = max(ans, f[A[j]]);
}
return ans;
}
