#include "sequence.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
using namespace std;
int sequence(int n, vector<int> a) {
int ans = 0;
int mid = n - 1;
for(int i = 0;i<n - 1;++i) if(a[i] > a[i + 1]){ mid = i; break; }
map<int, int> mp1, mp2;
for(int i = 0;i<mid;++i) ans = max(ans, ++mp1[a[i]]);
for(int i = mid + 1;i<n;++i) ans = max(ans, ++mp2[a[i]]);
map<int, int> freq;
freq[a[mid]] += 1;
int cnt = 1;
int l, r;
l = r = mid;
for(int i = a[mid];i;--i){
for(int j = l - 1;~j;--j){
if(a[j] == i) freq[i] += 1, l = j, cnt += 1;
else break;
}
for(int j = r + 1;j<n;++j){
if(a[j] == i) freq[i] += 1, r = j, cnt += 1;
else break;
}
int x = n - (cnt - freq[i]);
int y = cnt - freq[i];
if(x >= y) ans = max(ans, freq[i]);
}
return ans;
}
/*
7
1 2 3 1 2 1 3
9
1 1 2 3 4 3 2 1 1
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/
