#include <vector>
using namespace std;
#define pb push_back
struct range{
int l, r;
int idx;
int next;
};
vector<int> val;
vector<vector<int>> ed;
struct SegmentTree{
vector<int> t;
SegmentTree(int n){
t.resize(4*n+5);
}
void update(int v, int tl, int tr, int idx, int val){
if (tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (idx <= tm) update(v*2, tl, tm, idx, val);
else update(v*2+1, tm+1, tr, idx, val);
t[v] = t[v*2] + t[v*2+1];
}
int idx(int v, int tl, int tr, int k){
if (tl == tr){
return tl;
}
int tm = (tl + tr) / 2;
if (t[v*2] <= k) return idx(v*2, tl, tm, k);
else return idx(v*2+1, tm+1, tr, k - t[v*2]);
}
};
int buildTree(int n, int c, int*& s, int*& e){
int idx = n;
vector<int> cur(n);
SegmentTree tree(n);
for (int i = 0; i < n; ++i) {
tree.update(1, 0, n-1, i, 1);
cur[i] = i;
}
for (int i = 0; i < c; ++i) {
for (int j = s[i]; j <= e[i]; ++j) {
int k = cur[tree.idx(1, 0, n-1, j)];
ed[idx].pb(k);
}
int k = cur[tree.idx(1, 0, n-1, s[i])];
cur[k] = idx;
for (int j = s[i]+1; j < e[i]; ++j) {
tree.update(1, 0, n-1, j, 0);
}
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;
}
