#include <vector>
std::vector<int> children[200005];
int N;
int st[200005];
int query(int a,int b){
int res=0;
for(a+=N-1,b+=N-1;a<b;a>>=1,b>>=1){
if(a&1) res=std::max(res,st[a++]);
if(b&1) res=std::max(res,st[--b]);
}
return res;
}
int size[200005];
int depth[200005];
int deep[200005];
int R;
void dfs1(int node){
size[node]=1;
if(node<N){
deep[node]=node;
}
for(int child:children[node]){
dfs1(child);
if(depth[child]+1>depth[node]){
depth[node]=depth[child]+1;
deep[node]=deep[child];
}
size[node]+=size[child];
}
}
std::pair<int,int> best(-1,-1);
void dfs2(int node,int prefix,int suffix){
if(query(prefix,N-1-suffix)<=R){
best=std::max(best,{depth[node],-deep[node]});
}
suffix+=size[node];
for(int child:children[node]){
suffix-=size[child];
dfs2(child,prefix,suffix);
prefix+=size[child];
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
::N=N;
::R=R;
std::vector<int> stand;
for(int i=0;i<N;i++){
stand.push_back(i);
}
for(int i=0;i<C;i++){
for(int j=S[i];j<=E[i];j++){
children[N+i].push_back(stand[S[i]]);
stand.erase(stand.begin()+S[i]);
}
stand.insert(stand.begin()+S[i],N+i);
}
for(int i=0;i<N-1;i++){
st[N-1+i]=K[i];
}
for(int i=N-2;i>0;i--){
st[i]=std::max(st[i<<1],st[i<<1|1]);
}
dfs1(N+C-1);
dfs2(N+C-1,0,0);
return -best.second;
}
