#include <vector>
using namespace std;
#define pb push_back
struct range{
int l, r;
int idx;
};
vector<int> val;
vector<vector<int>> ed;
int buildTree(int n, int c, int*& s, int*& e){
int idx = n;
vector<range> cur(n);
for (int i = 0; i < n; ++i) {
cur[i].l = cur[i].r = cur[i].idx = i;
}
for (int i = 0; i < c; ++i) {
for (int j = s[i]; j <= e[i]; ++j) {
ed[idx].pb(cur[j].idx);
}
cur[s[i]].r = cur[e[i]].r;
cur[s[i]].idx = idx;
int k = e[i] - s[i];
for (int j = s[i] + 1; j <= e[i]; ++j) {
if (j + k < n) cur[j] = cur[j + k];
}
idx++;
}
return idx-1;
}
void dfs(int v){
for (auto x : ed[v]){
dfs(x);
val[v] = max(val[v], val[x]);
}
}
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
val.resize(2*n);
ed.resize(2*n);
int m = buildTree(n, c, s, e);
int mx = 0, ans = 0;
for (int i = 0; i < n; ++i) {
val.assign(2*n+1, 0);
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];
}
dfs(m);
int cnt = 0;
for (int j = 0; j <= m; ++j) {
if (val[j] == r) cnt++;
}
if (cnt > mx) {
ans = i;
mx = cnt;
}
}
return ans;
}
