#include "sequence.h"
#include <vector>
#include "bits/stdc++.h"
#define f1(n) for(int i=0;i<n;i++)
#define f3(n) for(int j=0;j<n;j++)
#define f2(m,n,q) for(int i=m;i<n;i++)
#define f4(m,n,q) for(int j=m;j<n;j++)
using namespace std;
int sequence(int n, vector<int> a) {
int ans=0,mid=n-1,mx=0;
f1(n-1)if (a[i]>a[i+1]){mid=i;break;}
map<int,int>mp,mp1;
f1(mid){mp[a[i]]++;ans=max(ans,mp[a[i]]);}
f2(mid+1,n,1){mp1[a[i]]++;ans=max(ans,mp1[a[i]]);}
map<int,int>frq;
frq[a[mid]]++;
int cnt=1;
int l=mid,r=mid;
for (int i=a[mid];i>=1;i--) {
for(int j=l-1;j>=0;j--) {
if (a[j]==i){frq[a[j]]++;l=j;cnt++;}
else break;
}
for(int j=r+1;j<n;j++)
if(a[j]==i){frq[a[j]]++;r=j;cnt++;}
else break;
int x=n-cnt+frq[i],y=cnt-frq[i];
if(x>=y)ans=max(ans,frq[i]);
}
return ans;
}
