#include<bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define pii pair<int, int>
typedef tree<
pair<int,int>,
null_type,
less<pair<int,int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
struct AddTree{
vector<int> tr;
int bar= 1;
void init(int _sz){
while(bar<_sz){
bar*=2;
}
tr.resize(2*bar, 0);
}
void add(int l, int r, int v){
l+=bar;
r+=bar+1;
int res= 0;
for(; l<r; l/=2, r/=2){
if(l%2==1){
tr[l++]+=v;
}
if(r%2==1){
tr[--r]+=v;
}
}
}
int get(int id){
id+=bar;
int res= 0;
for(int i = id; i>=1; i/=2){
res+=tr[i];
}
return res;
}
};
struct Tree{
vector<int> tr;
int bar= 1;
void init(int _sz){
while(bar<_sz){
bar*=2;
}
tr.resize(2*bar, 0);
}
int get(int l, int r){
l+=bar;
r+=bar+1;
int res= 0;
for(; l<r; l/=2, r/=2){
if(l%2==1){
res= max(res, tr[l++]);
}
if(r%2==1){
res= max(res, tr[--r]);
}
}
return res;
}
void upd(){
for(int i = bar-1; i>=1; i--){
tr[i] = max(tr[i*2], tr[i*2+1]);
}
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
ordered_set os;
vector<pii> affected;
for(int i = 0; i<N; i++){
os.insert(pii(i, i));
}
for(int i = 0; i<C; i++){
int l = S[i];
int r= E[i];
auto it = os.find_by_order(l);
auto itend = os.find_by_order(r);
pii interval = {it->first, itend->second};
affected.push_back(interval);
for(int i = l; i<=r; i++){
os.erase(os.find_by_order(l));
}
os.insert(interval);
}
Tree cur;
cur.init(N);
for(int i = 0; i<N-1; i++){
cur.tr[i+cur.bar] = K[i];
}
cur.upd();
AddTree tr;
tr.init(N);
for(int i = 0; i<C; i++){
//case 2: knight in the interval
int winer = cur.get(affected[i].first, affected[i].second-1);
//cout<<"winner "<<winer<<endl;
if(winer<=R){
tr.add(affected[i].first, affected[i].second, 1);
}
}
pii best = {-1, 0};
for(int i = 0; i<N; i++){
if(tr.get(i)>best.first){
best.first = tr.get(i);
best.second = i;
}
}
return best.second;
}
