#include<bits/stdc++.h>
using namespace std;
const int M=1<<18;
const int X=1e5+10;
struct UWU{
vector<int> s,lz;
void init(){s.resize(M,0),lz.resize(M,-1);}
void pushlz(int l,int r,int idx){
if(lz[idx]==-1) return;
s[idx]=lz[idx]*(r-l+1);
if(l!=r) lz[idx*2]=lz[idx],lz[idx*2+1]=lz[idx];
lz[idx]=-1;
}
void build(int l,int r,int idx){
if(l==r){
s[idx]=1;
return;
}
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
s[idx]=s[idx*2]+s[idx*2+1];
}
void update(int l,int r,int idx,int a,int b,int val){
pushlz(l,r,idx);
if(a>r || b<l) return;
if(a<=l && b>=r){
lz[idx]=val;
pushlz(l,r,idx);
return;
}
int m=(l+r)/2;
update(l,m,idx*2,a,b,val);
update(m+1,r,idx*2+1,a,b,val);
s[idx]=s[idx*2]+s[idx*2+1];
}
int query(int l,int r,int idx,int a,int b){
pushlz(l,r,idx);
if(a>r || b<l) return 0;
if(a<=l && b>=r) return s[idx];
int m=(l+r)/2;
return query(l,m,idx*2,a,b)+query(m+1,r,idx*2+1,a,b);
}
int walk(int l,int r,int idx,int w){
pushlz(l,r,idx);
if(l==r) return l;
int m=(l+r)/2;
pushlz(l,m,idx*2),pushlz(m+1,r,idx*2+1);
if(w>s[idx*2]) return walk(m+1,r,idx*2+1,w-s[idx*2]);
return walk(l,m,idx*2,w);
}
}fl,fr,hode;
int cnt[X],cs[X],ce[X],p[X],ret[X];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for(int i=0;i<N-1;i++) cnt[K[i]]++;
int id=0;
while(cnt[id]) id++;
for(int i=0;i<N-1;i++){
if(K[i]>id) p[i]++;
}
for(int i=1;i<N;i++) p[i]+=p[i-1];
fl.init(),fr.init(),hode.init();
fl.build(0,N-1,1);
fr.build(0,N-1,1);
for(int i=0;i<C;i++){
cs[i]=fl.walk(0,N-1,1,S[i]+1);
ce[i]=fr.walk(0,N-1,1,E[i]+1);
fl.update(0,N-1,1,S[i]+1,E[i],0);
fr.update(0,N-1,1,S[i],E[i]-1,0);
}
for(int i=0;i<C;i++){
if(p[ce[i]-1]-p[cs[i]-1]==0) ret[cs[i]]++,ret[ce[i]+1]--;
}
for(int i=1;i<N;i++) ret[i]+=ret[i-1];
int ans=-1,pi=67;
for(int i=0;i<N;i++){
if(ret[i]>ans){
ans=ret[i];
pi=i;
}
}
return pi;
}
