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