#include <bits/stdc++.h>
using namespace std;
struct qry{
int l, r, id;
};
int root;
vector<int> ch[200005];
int par[200005];
int order[200005], sz[200005], pos[200005];
int segR[800005], nodeid[200005], segS[800005];
void updR(int tar, int val, int id, int l, int r) {
if (l == r) {
segR[id] = val;
return;
}
int mid = (l+r)/2;
if (tar <= mid) updR(tar,val,id*2,l,mid);
else updR(tar,val,id*2+1,mid+1,r);
segR[id] = segR[id*2] + segR[id*2+1];
}
int qryR(int tar, int id, int l, int r) {
if (l == r) return l;
int mid = (l+r)/2;
if (tar < segR[id*2]) return qryR(tar,id*2,l,mid);
else return qryR(tar-segR[id*2],id*2+1,mid+1,r);
}
void updS(int tar, int val, int id, int l, int r) {
if (l == r) {
segS[id] = val;
return;
}
int mid = (l+r)/2;
if (tar <= mid) updS(tar,val,id*2,l,mid);
else updS(tar,val,id*2+1,mid+1,r);
segS[id] = segS[id*2] + segS[id*2+1];
}
int qryS(int t1, int t2, int id, int l, int r) {
if (r < t1 || t2 < l) return 0;
if (t1 <= l && r <= t2) return segS[id];
int mid = (l+r)/2;
return qryS(t1,t2,id*2,l,mid)+qryS(t1,t2,id*2+1,mid+1,r);
}
void maketree(int N, int C, int *S, int *E) {
for (int i = 0; i < N; i++) nodeid[i] = i;
for (int i = 0; i < N; i++) updR(i,1,1,0,N-1);
for (int i = 0; i < C; i++) {
root = N+i;
vector<int> tmp;
for (int j = S[i]; j <= E[i]; j++) tmp.push_back(qryR(j,1,0,N-1));
for (int j = 1; j < int(tmp.size()); j++) updR(tmp[j],0,1,0,N-1);
for (int j = 0; j < int(tmp.size()); j++) {
ch[root].push_back(nodeid[tmp[j]]);
par[nodeid[tmp[j]]] = root;
}
nodeid[tmp[0]] = root;
}
}
void dfs(int id) {
static int T = 0;
pos[id] = T;
order[T++] = id;
sz[id] = 1;
for (auto i : ch[id]) {
dfs(i);
sz[id] += sz[i];
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
maketree(N,C,S,E);
dfs(root);
int mx = -1, ans = -1;
for (int i = 1; i < N; i++) updS(pos[i], K[i-1]>R?1:0, 1, 0, N-1);
for (int i = 0; i < N; i++) {
int wins = 0, cur = i, doneroot = 0;
while (!doneroot) { //optimize using binary lifting O(log N)
bool ok = !qryS(pos[cur],pos[cur]+sz[cur]-1,1,0,N-1);
wins += ok;
if (cur == root) doneroot = 1;
cur = par[cur];
}
if (wins > mx) {
mx = wins;
ans = i;
}
int tmp1 = qryS(pos[i],pos[i],1,0,N-1), tmp2 = qryS(pos[i+1],pos[i+1],1,0,N-1);
updS(pos[i],tmp2,1,0,N-1), updS(pos[i+1],tmp1,1,0,N-1);
}
return ans;
}
