#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int fw[MAXN], nums;
void fupdate(int p, int v){
while (p <= nums){
fw[p] += v;
p += (p & (-p));
}
}
int fquery(int p){
int ans = 0;
while (p){
ans += fw[p];
p -= (p & (-p));
}
return ans;
}
struct node{
int s, e, m, val;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1, val = 0;
if (s != e){
l = new node(s, m);
r = new node(m + 1, e);
}
}
void update(int p, int v){
if (s == e){
val = v; return;
}
else if (p <= m) l->update(p, v);
else r->update(p, v);
val = max(l->val, r->val);
}
int query(int x, int y){
if (x == s && y == e) return val;
else if (y <= m) return l->query(x, y);
else if (x > m) return r->query(x, y);
else return max(l->query(x, m), r->query(m + 1, y));
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
nums = N;
set<int> spos;
for (int i = 1; i <= nums; i++){
fupdate(i, 1);
spos.insert(i);
}
spos.insert(nums + 1);
vector<pair<int, int>> rcoords(C);
for (int i = 0; i < C; i++){
int s = S[i], e = E[i], l = 1, r = nums, rs, re;
s++; e++;
while (l <= r){
int m = (l + r) >> 1;
if (fquery(m) >= s){
rs = m;
r = m - 1;
}
else l = m + 1;
}
auto it = spos.lower_bound(rs); it++;
for (int j = s + 1; j <= e; j++, it = spos.erase(it)) fupdate(*it, -1);
re = (*it) - 1;
rcoords[i] = {rs, re};
}
node *root = new node(1, nums - 1);
for (int i = 1; i < nums; i++) root->update(i, K[i - 1]);
vector<int> cumv(nums + 1);
for (auto &[s, e] : rcoords)
if (root->query(s, e - 1) < R){
cumv[s]++; cumv[e + 1]--;
}
int ans = -1, ind, curr = 0;
for (int i = 1; i <= nums; i++){
curr += cumv[i];
if (curr > ans){
ans = curr;
ind = i;
}
}
return ind - 1;
}
