#include<bits/stdc++.h>
#include<bits/extc++.h>
#define mem(x,i) memset(x,i,sizeof(x))
#define dbg(x) cerr<<#x<<" = "<<x<<'\n';
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
using namespace std;
using namespace __gnu_pbds;
tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> tr;
vector<pii> in[100005], out[100005];
int seg[200005];
void build(int N,int *K){
for(int i=N;i<2*N;i++) seg[i] = K[i-N];
for(int i=N-1;i>0;i--) seg[i] = max(seg[i*2], seg[i*2+1]);
}
int query(int N,int l,int r){
int ans = -1;
for(l+=N,r+=N+1;l<r;l>>=1,r>>=1){
if(l&1) ans = max(ans, seg[l++]);
if(r&1) ans = max(ans, seg[--r]);
}
return ans;
}
int cnt[100005];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for(int i=0;i<N;i++) tr.insert({i,i});
build(N-1,K);
for(int i=0;i<C;i++){
auto fr = tr.find_by_order(S[i]), ba = tr.find_by_order(E[i]);
int L = fr->fi, R = ba->se;
auto iter = fr;
while(iter != ba) iter = tr.erase(iter);
tr.erase(iter);
tr.insert({L,R});
S[i] = L, E[i] = R;
int rmq = query(N-1,S[i],E[i]-1);
in[S[i]].pb(rmq,++cnt[rmq]);
out[E[i]+1].pb(rmq,cnt[rmq]);
//cout<<S[i]<<" "<<E[i]<<" "<<rmq<<'\n';
}
tr.clear();
int ans = 0, mx = 0;
for(int i=0;i<N;i++){
for(auto x:in[i]) tr.insert(x);
for(auto x:out[i]) tr.erase(x);
int rk = tr.order_of_key({R,0});
//cout<<i<<" "<<rk<<'\n';
if(rk > mx){
mx = rk;
ans = i;
}
}
return ans;
}
