#include <bits/stdc++.h>
using namespace std;
const int MXN = 200005;
int tree[MXN * 4];
void build(int node, int l, int r) {
if (l == r) {
tree[node] = 1;
return;
}
int mid = (l + r) >> 1;
build(node << 1, l, mid);
build(node << 1 | 1, mid + 1, r);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
void update(int node, int l, int r, int pos) {
if (l == r) {
tree[node] = 0;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(node << 1, l, mid, pos);
else update(node << 1 | 1, mid + 1, r, pos);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
int get(int node, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (tree[node << 1] >= k) return get(node << 1, l, mid, k);
return get(node << 1 | 1, mid + 1, r, k - tree[node << 1]);
}
int GetBestPosition(int n, int c, int R, int *K, int *S, int *E) {
vector<int> pref(n + 1, 0);
for (int i = 0; i < n - 1; i++) {
pref[i + 1] = pref[i] + (K[i] > R);
}
build(1, 1, n);
vector<int> jump(n + 1);
for (int i = 1; i <= n; i++) jump[i] = i + 1;
vector<int> d(n + 2, 0);
for (int i = 0; i < c; i++) {
int l = get(1, 1, n, S[i] + 1);
int r = get(1, 1, n, E[i] + 1);
for (int j = jump[l]; j < r;) {
update(1, 1, n, j);
int nxt = jump[j];
jump[j] = jump[r];
j = nxt;
}
jump[l] = jump[r];
if (pref[r - 1] - pref[l-1] == 0) {
d[l]++;
d[r + 1]--;
}
}
int mx = -1, best = 0, cur = 0;
for (int i = 1; i <= n; i++) {
cur += d[i];
if (cur > mx) {
mx = cur;
best = i - 1;
}
}
return best;
}
