#include<bits/stdc++.h>
using namespace std;
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});
}
vector<int> sweep(N+1);
for(int i = 0; i < C; ++i){
int l = x[S[i]].first;
int r = x[E[i]].second;
x.erase(x.begin()+S[i], x.begin()+E[i]+1);
x.insert(x.begin() + S[i], {l, 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;
}
