#include <bits/stdc++.h>
using namespace std;
const int maxN = 100005;
struct Aint {
int n;
int v[4 * maxN];
int lazy[4 * maxN];
void build(int nod, int st, int dr) {
lazy[nod] = 0;
if (st == dr) {
v[nod] = 1;
return;
}
int med = (st + dr) / 2;
build(2 * nod, st, med);
build(2 * nod + 1, med + 1, dr);
v[nod] = v[2 * nod] + v[2 * nod + 1];
}
void propag(int nod) {
if (!lazy[nod]) {
return;
}
v[2 * nod] = 0;
v[2 * nod + 1] = 0;
lazy[2 * nod] = 1;
lazy[2 * nod + 1] = 1;
lazy[nod] = 0;
}
void update(int nod, int st, int dr, int ust, int udr) {
if (ust <= st && dr <= udr) {
v[nod] = 0;
lazy[nod] = 1;
return;
}
propag(nod);
int med = (st + dr) / 2;
if (ust <= med) {
update(2 * nod, st, med, ust, udr);
}
if (med < udr) {
update(2 * nod + 1, med + 1, dr, ust, udr);
}
v[nod] = v[2 * nod] + v[2 * nod + 1];
}
void update(int st, int dr) {
update(1, 1, n, st, dr);
}
int query(int nod, int st, int dr, int poz) {
if (st == dr) {
return st;
}
propag(nod);
int med = (st + dr) / 2;
if (v[2 * nod] >= poz) {
return query(2 * nod, st, med, poz);
}
return query(2 * nod + 1, med + 1, dr, poz - v[2 * nod]);
}
int findKth(int k) {
return query(1, 1, n, k);
}
void init(int N) {
n = N;
build(1, 1, n);
}
}aint;
struct RMQ {
int n;
int rmq[20][maxN];
int lg[maxN];
void build() {
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
rmq[j][i] = max(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
}
}
}
int query(int l, int r) {
int len = r - l + 1;
int x = lg[len];
return max(rmq[x][l], rmq[x][r - (1 << x) + 1]);
}
void init(int N, int v[]) {
n = N;
for (int i = 1; i <= n; i++) {
rmq[0][i] = v[i - 1];
}
build();
for (int i = 2; i <= n; i++) {
lg[i] = lg[i/2] + 1;
}
}
}rmq;
int mars[maxN];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
aint.init(N + 1);
rmq.init(N - 1, K);
for (int i = 0; i < C; i++) {
S[i]++;
E[i]++;
S[i] = aint.findKth(S[i]);
E[i] = aint.findKth(E[i] + 1) - 1;
aint.update(S[i] + 1, E[i]);
int maxi = rmq.query(S[i], E[i] - 1);
if (maxi < R) {
mars[S[i]]++;
mars[E[i]]--;
}
}
int best = 1;
for (int i = 1; i < N; i++) {
mars[i] += mars[i - 1];
if (mars[i] > mars[best]) {
best = i;
}
}
return best - 1;
}
