#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 11;
struct BIT{
int bit[MAXN] = {};
void add(int p, int v){
++p; for(int i = p; i < MAXN; i += i & -i) bit[i] += v;
}
int qry(int p){
++p; int r = 0; for(int i = p; i; i -= i & -i) r += bit[i];
return r;
}
int bs(int v){
int p = 0, s = 0; for(int j = 19; j >= 0; j--) if(p + (1 << j) < MAXN && s + bit[p + (1 << j)] <= v) s += bit[p + (1 << j)], p += (1 << j);
return p;
}
} bit;
struct ST{
int st[20][MAXN];
void init(int N, int *K){
for(int i = 0; i < N; i++) st[0][i] = K[i];
for(int j = 1; j < 20; j++){
for(int i = 0; i <= N - (1 << j); i++){
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
}
}
}
int qry(int l, int r){
if(l > r) return -(1 << 30);
int d = __lg(r - l + 1);
return max(st[d][l], st[d][r - (1 << d) + 1]);
}
} RMQ;
bool isMax(int i, int R, int l, int r){
assert(l <= i && i <= r);
return R > RMQ.qry(l, r - 1);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for(int i = 0; i < N; i++) bit.add(i, 1);
for(int i = 0; i < C; i++){
int l = S[i] == 0 ? 0 : bit.bs(S[i] - 1) + 1;
int r = bit.bs(E[i]);
for(int j = E[i] - 1; j >= S[i]; j--){
bit.add(bit.bs(j), -1);
}
S[i] = l, E[i] = r;
}
RMQ.init(N, K);
int mx = -1, ans = -1;
for(int i = 0; i < N; i++){
int op, ed, l, r;
l = 0, r = C;
while(l != r){
int mid = (l + r) / 2;
bool ok = S[mid] <= i && i <= E[mid];
if(ok){
r = mid;
}else{
l = mid + 1;
}
}
op = l;
l = op, r = C;
while(l != r){
int mid = (l + r + 1) / 2;
bool ok = isMax(i, R, S[mid - 1], E[mid - 1]);
if(ok){
l = mid;
}else{
r = mid - 1;
}
}
ed = l;
int res = ed - op;
if(res > mx){
mx = res;
ans = i;
}
}
return ans;
}
