#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e5 + 10;
int st[17][MAXN];
int query(int l, int r) {
int k = 32 - __builtin_clz(r-l+1) - 1; return max(st[k][l], st[k][r - (1<<k) + 1]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int dsu[N];
for(int i=0; i<N; i++) dsu[i] = i;
for(int i=0; i<C; i++) {
int lb = 0, rb = N - 1;
while(lb < rb) {
int mid = (lb + rb) >> 1;
if(dsu[mid] >= S[i]) rb = mid;
else lb = mid + 1;
}
int lb2 = 0, rb2 = N - 1;
while(lb2 < rb2) {
int mid = (lb2 + rb2 + 1) >> 1;
if(dsu[mid] <= E[i]) lb2 = mid;
else rb2 = mid - 1;
}
for(int j=lb + 1; j<=lb2; j++) dsu[j] = dsu[lb];
for(int j=lb2 + 1; j<N; j++) dsu[j] -= (E[i] - S[i]);
S[i] = lb, E[i] = lb2;
}
/*
for(int i=0; i<C; i++) {
cout << "Range #" << i <<": " << S[i] << " " << E[i] << "\n";
}
*/
int opt_cnt = 0, opt_id = 0;
int d[N + 1];
for(int i=0; i<N + 1; i++) d[i] = 0;
for(int i=0; i<N-1; i++) st[0][i] = K[i];
for(int i=1; i<17; i++) {
for(int j=0; j<N-1 && j + (1<<i) - 1 < N - 1; j++) {
st[i][j] = max(st[i-1][j], st[i-1][j+(1<<(i-1))]);
}
}
for(int i=0; i<C; i++) {
if(query(S[i], E[i] - 1) < R) {
d[S[i]]++;
d[E[i] + 1]--;
}
}
int cur = 0;
for(int i=0; i<N; i++) {
cur += d[i];
if(cur > opt_cnt) {
opt_cnt = cur, opt_id = i;
}
}
return opt_id;
}
