#include <vector>
using namespace std;
#define pb push_back
const int lg = 25;
vector<int> l, r;
vector<vector<int>> pr;
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 k){
if (tl == tr){
t[v] = k;
return;
}
int tm = (tl + tr) / 2;
if (idx <= tm) update(v*2, tl, tm, idx, k);
else update(v*2+1, tm+1, tr, idx, k);
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 sum(int v, int tl, int tr, int l, int r){
if (tl == l && tr == r){
return t[v];
}
int tm = (tl + tr) / 2;
int res = 0;
if (l <= tm) res += sum(v*2, tl, tm, l, min(r, tm));
if (r > tm) res += sum(v*2+1, tm+1, tr, max(l, tm+1), r);
return res;
}
};
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) {
vector<int> v;
for (int j = s[i]; j <= e[i]; ++j) {
int k = tree.idx(1, 0, n-1, j);
v.pb(k);
ed[idx].pb(cur[k]);
}
for (int j = s[i]; j <= e[i]; ++j) {
cur[v[j - s[i]]] = idx;
if (j != s[i]) tree.update(1, 0, n-1, v[j - s[i]], 0);
}
idx++;
}
return idx-1;
}
void dfs(int v, int p){
pr[0][v] = p;
for (int i = 1; i < lg; ++i) {
if (pr[i-1][v] == -1) continue;
pr[i][v] = pr[i-1][pr[i-1][v]];
}
l[v] = v;
for (auto x : ed[v]){
dfs(x, v);
l[v] = min(l[v], l[x]);
r[v] = max(r[v], r[x]);
}
if (r[v] == 0) r[v] = l[v];
}
void init(int n){
ed.resize(2*n);
l.resize(2*n);
r.resize(2*n);
pr.resize(lg);
for (int i = 0; i < lg; ++i) {
pr[i].resize(2*n);
pr[i].assign(2*n, -1);
}
}
int GetBestPosition(int n, int c, int rk, int *k, int *s, int *e) {
init(n);
int m = buildTree(n, c, s, e);
int mx = 0, ans = 0;
SegmentTree tree(n);
for (int i = 0; i < n - 1; ++i) {
tree.update(1, 0, n-1, i+1, k[i]);
}
for (int i = 0; i < n; ++i) {
int cur = i;
int res = 0;
for (int j = lg-1; j >= 0; --j) {
if (pr[j][cur] == -1) continue;
int p = pr[j][cur];
int x = tree.sum(1, 0, n-1, l[p], r[p]);
if (x == 0) cur = pr[j][cur], res += (1 << j);
}
if (res > mx) mx = res, ans = i;
if (i == n-1) continue;
tree.update(1, 0, n-1, i+1, 0);
if (k[i] > rk) tree.update(1, 0, n-1, i, 1);
}
return ans;
}
