#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int N = 2e5 + 5;
int n;
int lz[4 * N], t[4 * N], fw[N];
void upd(int u, int id, int l, int r) {
if(l > id || r < id) return;
if(l == r) {
t[u] ^= 1;
return;
}
int mid = (l + r) / 2;
upd(2 * u, id, l, mid); upd(2 * u + 1, id, mid + 1, r);
t[u] = t[2 * u] + t[2 * u + 1];
}
int get(int u, int l, int r, int id) {
if(l == r) return l;
int mid = (l + r) / 2;
if(t[2 * u] >= id) return get(2 * u, l, mid, id);
return get(2 * u + 1, mid + 1, r, id - t[2 * u]);
}
void upd(int id, int v) {
++id;
for(id; id <= n; id += id & (-id)) fw[id] += v;
}
int get(int id) {
int ans = 0; ++id;
for(id; id >= 1; id -= id & (-id)) ans += fw[id];
return ans;
}
int GetBestPosition(int nn, int C, int R, int *K, int *ST, int *E) {
set<int> s, S, bad;
n = nn;
for(int i = 0; i < n; i++) s.insert(i), S.insert(i), upd(1, i, 0, n - 1);
for(int i = 0; i < n - 1; i++) {
if(K[i] > R) bad.insert(i);
}
bad.insert(n + 1); s.insert(n + 1); S.insert(n + 1);
pii ans; ans.f = -1;
for(int i = 0; i < C; i++) {
ST[i] = (ST[i] == 0 ? 0 : get(1, 0, n - 1, ST[i]) + 1); E[i] = get(1, 0, n - 1, E[i] + 1);;
while(*s.upper_bound(ST[i] - 1) < E[i]) {
int x = *s.upper_bound(ST[i] - 1);
s.erase(x);
upd(1, x, 0, n - 1);
}
if(*bad.upper_bound(ST[i] - 1) >= E[i]) upd(ST[i], 1), upd(E[i] + 1, -1);
else {
while(*S.upper_bound(ST[i] - 1) <= E[i]) {
ans = max(ans, {get(*S.upper_bound(ST[i] - 1)), -*S.upper_bound(ST[i] - 1)});
S.erase(*S.upper_bound(ST[i] - 1));
}
}
}
while(S.size()) ans = max(ans, {get(*S.begin()), -*S.begin()}), S.erase(*S.begin());
// cout << ans.f << " " << ans.s << endl;
return -ans.s;
}
