#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e5+5;
int up[MXN][25];
int t[MXN*4];
vector <int> lazy(4*MXN,-1);
int k[MXN];
int p[MXN];
void applay(int node, int val, int l, int r) {
t[node] = val*(r-l+1);
lazy[node] = val;
}
void push(int node, int l, int r){
if (lazy[node] != -1) {
int mid = (l+r)/2;
applay(node*2,lazy[node],l,mid);
applay(node*2+1,lazy[node],mid+1,r);
lazy[node] = -1;
}
}
void update(int node, int l, int r, int L, int R, int val) {
if (l > R || r < L) return;
if (l >= L && r <= R) {
applay(node, val, l, r);
return;
}
push(node, l, r);
int mid = (l + r) >> 1;
update(node<<1, l, mid, L, R, val);
update(node<<1|1, mid+1, r, L, R, val);
t[node] = t[node<<1] + t[node<<1|1];
}
int get(int node, int l, int r, int val) {
if (val <= 0) return l;
if (val >= t[node]) {
if (l == r) return l;
}
if (l == r) return l;
push(node, l, r);
int mid = (l + r) >> 1;
if (t[node<<1] >= val) return get(node<<1, l, mid, val);
return get(node<<1|1, mid+1, r, val - t[node<<1]);
}
int merge(int x, int y) {
if (k[x] > k[y]) return x;
return y;
}
int getmax(int l, int r) {
if (l > r) return -1;
int len = r - l + 1;
int lg = 31 - __builtin_clz(len);
int a = up[l][lg];
int b = up[r - (1<<lg) + 1][lg];
return merge(a,b);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for (int i = 0; i <= N+1; i++) p[i] = 0;
for (int i = 0; i < 4*N; i++) {
t[i] = 0;
lazy[i] = -1;
}
for (int i = 0; i < N-1; i++) {
k[i] = K[i];
up[i][0] = i;
}
for (int i = 1; i <= 20; i++) {
for (int j = 0; j + (1<<i) - 1 < N-1; j++) {
up[j][i] = merge(up[j][i-1],up[j+(1<<(i-1))][i-1]);
}
}
for (int i = 1; i <= N; i++) {
update(1,1,N,i,i,1);
}
for (int i = 0; i < C; i++) {
int l = get(1,1,N,S[i]+1);
int r = get(1,1,N,E[i]+1);
int mx =getmax(l-1,r-2);
if (mx != -1) mx = k[mx];
if (l < r) update(1,1,N,l+1,r,0);
if (mx < R) {
p[l]++;
p[r+1]--;
}
}
int ans = 1;
for (int i = 1; i <= N; i++) {
p[i] = p[i-1] + p[i];
if (p[ans] < p[i]) ans = i;
}
return ans-1;
}
