#include<bits/stdc++.h>
using namespace std;
struct lazysegtree{
vector<int> t;
vector<bool> lazy;
lazysegtree(int n){
t.assign(4 * (n+1), 0);
lazy.assign(4*(n+1), false);
build(1, 0, n);
}
void build(int no, int lo, int hi){
if(lo == hi){
t[no] = 1;
return;
}
int mid = lo + (hi - lo) / 2;
build(2*no, lo, mid);
build(2*no+1, mid+1, hi);
t[no] = t[2*no] + t[2*no+1];
}
void update(int no, int lo, int hi, int l, int r){
if(lo == l && hi == r){
t[no] = 0;
lazy[no] = 1;
return;
}
int mid = lo + (hi - lo) / 2;
//cout << no << " " << l << " " << r << " " << lo << " " << hi << endl;
//propagate(no);
if(r <= mid){
update(2*no, lo, mid, l, r);
}else if(l > mid){
update(2*no+1, mid+1, hi, l, r);
}else{
update(2*no, lo, mid, l, mid);
update(2*no+1, mid+1, hi, mid+1, r);
}
t[no] = t[2*no] + t[2*no+1];
}
int query(int no, int lo, int hi, int tar, int sum){
if(lo == hi){
return lo;
}
int mid = lo + (hi - lo) / 2;
//cout << no << " " << t[no] << " " << sum << tar << endl;
assert(t[no] + sum >= tar);
if(t[2*no]+sum >= tar){
return query(2*no, lo, mid, tar, sum);
}else{
sum += t[2*no];
return query(2*no+1, mid+1, hi, tar, sum);
}
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
vector<int> pref(N+1);
vector<int> suff(N+1);
vector<int> knights;
int defeat = 0;
for(int i = 0; i < N-1; ++i){
if(K[i] > R){
defeat++;
pref[i]++;
suff[i]++;
}
}
vector<pair<int, int>> x;
for(int i = 0; i < N; ++i){
pref[i+1] += pref[i];
suff[N-i-1] += suff[N-i];
x.push_back({i, i});
}
x.push_back({N, N});
vector<int> sweep(N+1);
lazysegtree tree(N);
for(int i = 0; i < C; ++i){
//cout << i << endl;
int l = tree.query(1, 0, N, S[i]+1, 0);
int r = tree.query(1, 0, N, E[i]+2, 0)-1;
//cout << l << " " << r << endl;
tree.update(1, 0, N, l+1, r);
if(l > 0){
if(pref[l-1] + suff[r] >= defeat){
sweep[l]++;
sweep[r+1]--;
}
}else{
if(suff[r] >= defeat){
sweep[l]++;
sweep[r+1]--;
}
}
}
int ans = -1;
int act = 0;
int pos = 0;
for(int i = 0; i <= N-1; ++i){
act += sweep[i];
if(act > ans){
ans = act;
pos = i;
}
}
return pos;
}
