#include <iostream>
#include <vector>
using namespace std;
const int N = (1<<17) + 1;
int cnt[N<<1], Par[N<<1][20], Mn[N], Mx[N], hei[N], num[N];
vector<int> nei[N<<1];
void insert(int i, int t, int cur = 1, int st = 1, int en = N){
if (i < st or i >= en)
return;
cnt[cur] += t;
if (en - st == 1)
return;
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
insert(i, t, lc, st, mid);
insert(i, t, rc, mid, en);
}
int get(int k, int cur = 1, int st = 1, int en = N){
if (en - st == 1)
return st;
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
if (cnt[lc] >= k)
return get(k, lc, st, mid);
return get(k - cnt[lc], rc, mid, en);
}
void dfs(int u, int p){
hei[u] = hei[p] + 1;
Par[u][0] = p;
for (int i=0;i<17;i++)
Par[u][i+1] = Par[Par[u][i]][i];
for (int i : nei[u])
dfs(i, u);
if (nei[u].size() > 0)
Mn[u] = Mn[nei[u].front()], Mx[u] = Mx[nei[u].back()];
}
int goUp(int u, int l, int r){
for (int i=17;i>=0;i--){
if (Par[u][i] != 0 and l <= Mn[Par[u][i]] and Mx[Par[u][i]] <= r)
u = Par[u][i];
}
return hei[u];
}
int GetBestPosition(int n, int c, int rnk, int k[], int s[], int e[]){
for (int i=1;i<=n;i++)
insert(i, 1), num[i] = Mn[i] = Mx[i] = i;
int cur = n + 1;
for (int i=0;i<c;i++){
int k = s[i] + 1, len = e[i] - s[i] + 1, lst;
while (len--){
insert(lst = get(k), -1);
nei[cur].push_back(num[lst]);
}
num[lst] = cur++;
insert(lst, 1);
}
dfs(cur - 1, 0);
int ans = 0, id = 0;
for (int i=0, l = -1, r = 0;i<n;i++){
r = max(r, i);
while (r < n - 1 and k[r] < rnk)
r++;
int h = hei[i + 1] - goUp(i + 1, l + 2, r + 1);
if (h > ans)
ans = h, id = i;
if (k[i] > rnk)
l = i;
}
return id;
}
