#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// sub 1-2, 49 points simple
int dfs(int node, int N, int R, vi &val, vvi &g) {
int res = 0;
for (int to : g[node]) {
res += dfs(to, N, R, val, g);
val[node] = max(val[node], val[to]);
}
if (node >= N && val[node] == R) ++res;
return res;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
vvi g(2 * N);
int nextNode = N - 1;
vector<int>root(N), alive(N, 1);
for (int i = 0; i < N; ++i) {
root[i] = i;
}
for (int i = 0; i < C; ++i) {
int node = -1, cnt = 0;
while (cnt <= S[i]) {
++node;
if (alive[node]) {
++cnt;
}
}
g[++nextNode].eb(root[node]);
root[node] = nextNode;
while (cnt <= E[i]) {
++node;
if (alive[node]) {
g[nextNode].eb(root[node]);
alive[node] = 0;
++cnt;
}
}
}
int best = 0, bestPos = 0;
for (int i = 0; i < N; ++i) {
vector<int>val(nextNode + 1, -1);
for (int j = 0; j < i; ++j) {
val[j] = K[j];
}
val[i] = R;
for (int j = i; j < N - 1; ++j) {
val[j + 1] = K[j];
}
int cur = dfs(nextNode, N, R, val, g);
if (cur > best) {
best = cur;
bestPos = i;
}
}
return bestPos;
}
