#include<algorithm>
#define pii pair<int,int>
using namespace std;
int r_T[400000];
int ans_T[400000];
int st[100001];
void m_r_T(int idx,int s,int e,int gs,int v){
if(e<gs||s==e)return;
r_T[2*idx]+=r_T[idx];r_T[2*idx+1]+=r_T[idx];r_T[idx]=0;
if(gs<=s){
r_T[idx]+=v;
return;
}
int m=s+e>>1;
m_r_T(2*idx,s,m,gs,v);
m_r_T(2*idx+1,m+1,e,gs,v);
}
int g_r_T(int idx,int s,int e,int g){
if(e<g||g<s)return 0;
if(s==e)return r_T[idx];
r_T[2*idx]+=r_T[idx];r_T[2*idx+1]+=r_T[idx];r_T[idx]=0;
int m=s+e>>1;
return g_r_T(2*idx,s,m,g)+g_r_T(2*idx+1,m+1,e,g);
}
void m_ans_T(int idx,int s,int e,int gs,int ge,int v){
if(e<gs||ge<s||s==e)return;
ans_T[2*idx]+=ans_T[idx];ans_T[2*idx+1]+=ans_T[idx];ans_T[idx]=0;
if(gs<=s&&e<=ge){
ans_T[idx]+=v;
return;
}
int m=s+e>>1;
m_ans_T(2*idx,s,m,gs,ge,v);
m_ans_T(2*idx+1,m+1,e,gs,ge,v);
}
pii g_ans_T(int idx,int s,int e){
if(s==e)return pii(ans_T[idx],s);
ans_T[2*idx]+=ans_T[idx];ans_T[2*idx+1]+=ans_T[idx];ans_T[idx]=0;
int m=s+e>>1;
pii t1=g_ans_T(2*idx,s,m),t2=g_ans_T(2*idx+1,m+1,e);
return t1.first>t2.first?t1:t2;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
for(int i=0;i<N-1;i++)st[i+1]=st[i]+(K[i]>R);
for(int i=0;i<C;i++){
if(S[i])S[i]+=g_r_T(1,0,N-1,S[i]);
E[i]+=g_r_T(1,0,N-1,E[i]);
m_r_T(1,0,N-1,S[i],E[i]-S[i]);
if(st[E[i]-1]-st[S[i]-1]==0)m_ans_T(1,0,N-1,S[i],E[i],1);
}
return g_ans_T(1,0,N-1).second;
}
