#include <bits/stdc++.h>
using namespace std;
vector<int> tree(100010*4,0);
void build(int n, int l, int r){
if(l==r){
tree[n]=1;
return;
}
int m=l+((r-l)/2);
build(n*2,l,m);
build(n*2+1,m+1,r);
tree[n]=tree[n*2]+tree[n*2+1];
return;
}
void update(int n, int ql, int qr, int l, int r){
if(ql>r || qr<l) return;
if(ql<=l && r<=qr){
tree[n]=0;
return;
}
int m=l+((r-l)/2);
update(n*2,ql,qr,l,m);
update(n*2+1,ql,qr,m+1,r);
tree[n]=tree[n*2]+tree[n*2+1];
}
int query(int n, int l, int r, int x, int i){
if(l==r)return l;
int m=l+((r-l)/2);
if(tree[2*n]+i>=x)return query(n*2,l,m,x,i);
else{
i+=tree[n*2];
return query(n*2+1,m+1,r,x,i);
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int ans=0;
vector<int> pMax(N+5,0),tmp(N+5,0),tmp2(N+5,0);
vector<pair<int,int>> ln;
int wins=0;
for(int i=0;i<N-1;i++){
if(K[i]>R){
tmp[i+1]++;
tmp2[i]++;
wins++;
}
}
for(int i=0;i<N;i++){
tmp[i+1]+=tmp[i];
tmp2[N-1-i]+=tmp2[N-i];
ln.push_back({i,i});
}
build(1,0, N);
for(int i=0;i<C;i++){
int l=query(1,0,N,S[i]+1,0);
int r=query(1,0,N,E[i]+2,0)-1;
update(1,l+1,r,0,N);
if(tmp[l]+tmp2[r]==wins){
pMax[l]++;
pMax[r+1]--;
}
}
int mx=pMax[0],bestWins=pMax[0];
for(int i=1;i<=N;i++){
mx+=pMax[i];
if(mx>bestWins){
bestWins=mx;
ans=i;
}
}
return ans;
}
