#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
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) {
vector<pii> affected;
map<int, pii> is_set_to;
for(int i = 0; i<N; i++){
is_set_to[i] = pii(i, i);
}
for(int i = 0; i<C; i++){
int l = S[i];
int r= E[i];
auto it = is_set_to.begin();
pii res= pii(0, 0);
for(int j = 0; it!=is_set_to.end(); j++, ++it){
if(j == l){
res.first = it->second.first;
}
if(j==r){
res.second = it->second.second;
}
}
for(int j = res.first; j<=res.second; j++){
is_set_to.erase(j);
}
is_set_to[res.first]= res;
affected.push_back(res);
//cout<<res.first<<" "<<res.second<<endl;
}
Tree tr;
tr.init(N);
pair<int, int> best = {0, 0};
for(int i = 0; i<N; i++){
//cout<<"pos "<<i<<endl;
int cur= 0;
for(int j = 0; j<i; j++){
tr.tr[j+tr.bar] = K[j];
}
tr.tr[i+tr.bar] = R;
for(int j = i+1; j<N; j++){
tr.tr[j+tr.bar] = K[j-1];
}
tr.upd();
for(int j = 0; j<C; j++){
if(affected[j].first<=i && i<=affected[j].second){
//cout<<"req "<<j<<" "<<"res "<<tr.get(affected[j].first, affected[j].second)<<endl;
if(tr.get(affected[j].first, affected[j].second) == R){
cur++;
//cout<<"wins "<<j<<endl;
}
}
}
if(cur>best.first){
best.first= cur;
best.second= i;
}
}
return best.second;
}
