#include <bits/stdc++.h>
using namespace std;
class fenwick_tree {
private:
int n;
vector<int> fenw;
public:
fenwick_tree(int _n) : n(_n) {
fenw.assign(n, 0);
}
void update(int x, int val) {
while (x < n) {
fenw[x] += val;
x += x & -x;
}
}
int query(int x) {
int ans = 0;
while (x > 0) {
ans += fenw[x];
x -= x & -x;
}
return ans;
}
int find(int x) {
int pos = 0, save = x;
for (int i = 20; i >= 0; i--) {
if (pos + (1 << i) >= n) continue;
if (fenw[pos + (1 << i)] < x) {
pos += (1 << i);
x -= fenw[pos];
}
}
return pos + (save > 0);
}
};
class segment_tree {
private:
struct node {
int l, r, val;
node *left, *right;
} *root;
node *build(int l, int r, int *a) {
if (l == r) return new node{l, r, a[l], nullptr, nullptr};
node *left = build(l, (l + r) / 2, a);
node *right = build((l + r) / 2 + 1, r, a);
return new node{l, r, max(left->val, right->val), left, right};
}
int query(int l, int r, node *cur) {
if (cur->l > r || cur->r < l) return -1;
if (cur->l >= l && cur->r <= r) return cur->val;
return max(query(l, r, cur->left), query(l, r, cur->right));
}
public:
segment_tree(int *a, int n) {
root = build(1, n, a);
}
int query(int l, int r) {
return query(l, r, root);
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
set<int> st;
fenwick_tree fenw(N + 1);
for (int i = 1; i <= N; i++) {
st.insert(i);
fenw.update(i, +1);
}
segment_tree seg(K - 1, N - 1);
vector<int> pre(N + 2, 0);
for (int i = 0; i < C; i++) {
S[i]++; E[i]++;
int l = fenw.find(S[i] - 1) + 1, r = fenw.find(E[i]);
auto it = st.lower_bound(l);
while (next(it) != st.end() && *next(it) <= r) {
fenw.update(*it, -1);
it = st.erase(it);
}
if (seg.query(l, r - 1) <= R) {
pre[l]++; pre[r + 1]--;
}
}
int ans = 0;
for (int i = 1; i <= N; i++) {
pre[i] += pre[i - 1];
if (pre[i] > pre[ans]) ans = i;
}
return max(ans - 1, 0);
}
