#include <bits/stdc++.h>
using namespace std;
struct qry{
int l, r, id;
};
int root;
vector<int> ch[200005];
int par[200005];
int ar[200005], order[200005], sz[200005], pos[200005];
qry range[200005];
void maketree(int N, int C, int *S, int *E) {
for (int i = 0; i < N; i++) range[i] = {i,i,i};
for (int i = 0; i < C; i++) {
range[S[i]].r = range[E[i]].r;
for (int j = S[i]; j <= E[i]; j++) {
ch[N+i].push_back(range[j].id);
par[range[j].id] = N+i;
}
range[S[i]].id = root = N+i;
for (int j = E[i]+1; j < N; j++) range[j-(E[i]-S[i])] = range[j];
E[i] = range[S[i]].r, S[i] = range[S[i]].l;
}
par[root] = 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); //try to make this less than O(N^2)
dfs(root);
int mx = -1, ans = -1;
for (int i = 1; i < N; i++) ar[i] = (K[i-1] > R ? 1 : 0);
for (int i = 0; i < N; i++) { //exhaust O(N)
int wins = 0, cur = i, doneroot = 0;
while (!doneroot) { //optimize using binary lifting O(log N)
bool ok = 1;
for (int j = pos[cur]; j < pos[cur]+sz[cur]; j++) {
if (ar[order[j]]) ok = 0; //optimize using segment tree O(log N)
}
wins += ok;
if (cur == root) doneroot = 1;
cur = par[cur];
}
if (wins > mx) {
mx = wins;
ans = i;
}
swap(ar[i],ar[i+1]);
}
return ans;
}
