#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 (tree[node] < k) return -1;
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 q, int m, int *K, int *L, int *R) {
vector<int> pref(n + 2, 0), jump(n + 2), d(n + 2, 0);
build(1, 1, n);
for (int i = 1; i <= n; i++) {
int K1 = (i < n) ? K[i - 1] : 2e9;
pref[i + 1] = pref[i] + (K1 > m);
jump[i] = i + 1;
}
for (int i = 0; i < q; i++) {
int l = get(1, 1, n, L[i] + 1);
int r = get(1, 1, n, R[i] + 2);
if (r == -1) r = n + 1;
for (int j = jump[l]; j < r; ) {
update(1, 1, n, j);
int next_j = jump[j];
jump[j] = r;
j = next_j;
}
jump[l] = r;
if (pref[l] == pref[r - 1]) {
d[l]++;
d[r]--;
}
}
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;
}
