#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define sc second
typedef pair<int,int> pii;
typedef tree< pii, null_type, less<pii>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
const int MAXN = 1e5+5;
int v[MAXN*2], id[MAXN*2], ans[MAXN*2], r[MAXN*2];
int GetBestPosition(int n, int c, int R, int *K, int *s, int *e) {
for(int i = 0; i < n-1; i++)v[i] = K[i] > R;
ordered_set st;
for(int i = 0; i < n; i++){
if(v[i] == 1)id[i] = i;
r[i] = i;
st.insert({i,i});
}
int novo = n, resp = 0, idresp = 0;
for(int i = 0; i < c; i++){
int x = e[i]-s[i], l;
for(int j = 0; j <= x; j++){
auto it = st.find_by_order(s[i]);
if(j == 0)l = it->fi;
v[novo] += v[it->sc];
id[novo] += id[it->sc];
ans[novo] = max(ans[it->sc], ans[novo]);
r[novo] = max(r[novo],r[it->sc]);
st.erase(it);
}
st.insert({l, novo});
if(v[novo] > 1 || (v[id[novo]] == 1 && id[novo] != r[novo])){ans[novo] = 0;}
else{
ans[novo]++;
if(resp < ans[novo]){
resp = ans[novo];
idresp = id[novo];
}
}
novo++;
}
return idresp;
}
