#include <bits/stdc++.h>
using namespace std;
int a[100001], s[100001], e[100001];
#define mp make_pair
#define pb push_back
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
vector<pair<int, int>> v;
int buffcnt = 0;
for (int i = 0; i < N - 1; i++) {
if (K[i] > R) {
s[i + 1]++;
e[i]++;
buffcnt++;
}
}
for (int i = 0; i < N; i++) {
s[i + 1] += s[i];
e[N - 1 - i] += e[N - i];
v.pb(mp(i, i));
}
for (int i = 0; i < C; i++) {
int l = v[S[i]].first;
int r = v[E[i]].second;
v.erase(v.begin() + S[i], v.begin() + E[i] + 1);
v.insert(v.begin() + S[i], mp(l, r));
if (s[l] + e[r] == buffcnt) {
a[l]++;
a[r+1]--;
}
}
int sum = a[0], mx = sum, bestpos = 0;
for (int i = 1; i <= N; i++) {
sum += a[i];
if (sum > mx) {
mx = sum;
bestpos = i;
}
}
return bestpos;
}
