#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
int N,C,R,nn,sum[MAXN],v,mx=-1;
int seg[MAXN*4],mxseg[MAXN*4];
int *K,*S,*E;
int query1(int lef,int rig,int lev,int x){
if(x==0) return -1;
if(lef==rig) return lef;
else{
int mid=lef+rig>>1;
if(seg[lev*2]>=x) return query1(lef,mid,lev*2,x);
else return query1(mid+1,rig,lev*2+1,x-seg[lev*2]);
}
}
void query2(int lef,int rig,int lev,int s,int e){
if(rig<s || e<lef) return;
if(s<=lef && rig<=e) seg[lev]=0;
else{
int mid=(lef+rig)/2;
query2(lef,mid,lev*2,s,e);
query2(mid+1,rig,lev*2+1,s,e);
seg[lev]=seg[lev*2]+seg[lev*2+1];
}
}
int query3(int lef,int rig,int lev,int s,int e){
if(rig<s || e<lef) return -1;
if(s<=lef && rig<=e) return mxseg[lev];
else{
int mid=lef+rig>>1;
return max(query3(lef,mid,lev*2,s,e),query3(mid+1,rig,lev*2+1,s,e));
}
}
int GetBestPosition(int iN, int iC, int iR, int *iK, int *iS, int *iE)
{
N=iN,C=iC,R=iR,K=iK,S=iS,E=iE;
for(nn=1;nn<N;nn*=2);
for(int i=0;i<N;i++) seg[i+nn]=1,mxseg[i+nn]=K[i];
for(int i=nn-1;i>=1;i--) seg[i]=seg[i*2]+seg[i*2+1],mxseg[i]=max(mxseg[i*2],mxseg[i*2+1]);
for(int i=0;i<C;i++){
int p2=query1(0,nn-1,1,E[i]+1),p1=query1(0,nn-1,1,S[i])+1;
query2(0,nn-1,1,p1,p2-1);
if(query3(0,nn-1,1,p1,p2-1)<=R) sum[p1]++,sum[p2+1]--;
}
int st=0;
for(int i=0;i<N;i++){
st+=sum[i];
if(mx<st){
mx=st;
v=i;
}
}
return v;
}
