#include "sequence.h"
#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> st;
int sequence(int n, std::vector<int> A) {
map<int,int> mp;
if(n <= 2000){
int ans = 0;
for(int i = 0;i < n;i++){
mp.clear();
st.clear();
for(int j = i;j < n;j++){
st.insert(A[j]);
mp[A[j]]++;
int a = *st.find_by_order((j - i) / 2), b = *st.find_by_order((j - i + 1) / 2);
ans = max({ans, mp[a], mp[b]});
}
}
return ans;
}
int ans = 0;
vector<int> B = A;
sort(B.begin(), B.end());
int d = n;
int c = B[(n - 1) / 2];
for(int i = 1;i < n;i++){
if(A[i] < A[i - 1]){
d = i;
break;
}
}
map<int,int> mp1, mp2;
for(int i = 0;i < d;i++)mp1[A[i]]++;
for(int i = d;i < n;i++)mp2[A[i]]++;
for(auto [i, j]: mp1)ans = max(ans, j);
for(auto [i ,j]: mp2)ans = max(ans, j);
for(int i = 0;i < n;i++){
if(A[i] >= c)ans = max(ans, mp1[A[i]] + mp2[A[i]]);
}
return ans;
}
