#include "sequence.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
#include <vector>
#define lg long long
using namespace std;
const lg N = 2e3+5;
int sequence(int nO, vector<int> a)
{
lg ans = 1;
map<lg, lg> inc, dec;
bool flag = true;
vector<int> v = a;
sort(v.begin(), v.end());
for(int i = 0; i < nO; i++)
{
if(flag) inc[a[i]]++;
else dec[a[i]]++;
if(i && a[i] < a[i-1])
{
flag = false;
}
}
for(auto it : inc)
{
auto it2 = lower_bound(v.begin(), v.end(), it.first)-v.begin();
if(it2 >= nO/2)
{
// cout << it.first << ' ' << it2 << '\n';
ans = max(ans, it.second+dec[it.first]);
}
ans = max(ans, it.second);
}
for(auto it : dec)
{
auto it2 = lower_bound(v.begin(), v.end(), it.first)-v.begin();
if(it2 >= nO/2)
{
// cout << it.first << '\n';
ans = max(ans, it.second+inc[it.first]);
}
ans = max(ans, it.second);
}
return ans;
}
/*
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
9
1 1 2 3 4 3 2 1 1
7
1 2 3 1 2 1 3
*/
