#include <vector>
#include <iostream>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
int aib[nmax],mx[nmax],wh[nmax],parinte[nmax],dp[nmax],opt[nmax],val[nmax],mxnorm[nmax],mxst[nmax],mxin[nmax],M[nmax];
int K[nmax],S[nmax],E[nmax];
int n,i,j,st,dr,act,nod,maxim,globalopt,mxx;
inline int lbit(int x)
{
return ((x^(x-1))&x);
}
void update(int poz,int val)
{
for(int idx=poz;idx<=n;idx+=lbit(idx))
aib[idx]+=val;
}
int get_kth(int k)
{
int poz=0,curr=0;
for(int p=16;p>=0;p--)
if(poz+(1<<p)<=n&&curr+aib[poz+(1<<p)]<k)
poz+=(1<<p),curr+=aib[poz];
poz++;
return poz;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n=N;globalopt=1;
for(i=0;i<n-1;i++)
{
update(i+1,1);
}
int tot=n;
for(i=1;i<=n;i++)
parinte[i]=R+i,opt[R+i]=i,dp[R+i]=0,val[i]=K[i-1];
for(i=0;i<C;i++)
{
st=S[i]+1;dr=E[i]+1;
for(j=dr;j>=st;j--)
{
if(j<=tot)
{
act=get_kth(j);
if(val[act]>mxnorm[i])
mxnorm[i]=val[act];
if(j<dr&&val[act]>mxin[i])
mxin[i]=val[act];
if(j<dr&&val[act]>mxst[i])
mxst[i]=val[act];
v[i].push_back(parinte[j]);
update(act,-1);
tot--;
}
}
if(st>1)
mxst[i]=max(mxst[i],val[get_kth(st-1)]);
tot++;
update(act,1);
parinte[act]=i;
val[act]=mxin[i];
M[v[i].size()]=-1;
for(j=v[i].size()-1;j>=0;j--)
{
M[j]=max(M[j+1],mxnorm[j]);
}
int S=-1;
for(j=0;j<v[i].size();j++)
{
nod=v[i][j];
S=max(S,mxst[nod]);
if(S<C&&mxin[nod]<C&&M[j+1]<C&&opt[nod])
{
if(dp[nod]+1>dp[i]||(dp[nod]+1==dp[i]&&opt[nod]<opt[i]))
dp[i]=dp[nod]+1,opt[i]=opt[nod];
}
}
if(dp[i]>mxx||(dp[i]==mxx&&opt[i]<globalopt))
globalopt=opt[i],mxx=dp[i];
}
return globalopt-1;
}
