#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int MAXN = 100007;
int n, ranks[MAXN], s[MAXN], e[MAXN];
struct Tree{
private:
vector <int> tree, lz;
public:
Tree(int n){
tree.assign(n*4, 0);
}
void build(int v, int l, int r){
if(l == r){
tree[v] = 1;
return;
}
int mid = (l+r) >> 1;
build(v<<1, l, mid);
build((v<<1)+1, mid+1, r);
tree[v] = tree[v<<1] + tree[(v<<1)+1];
}
void update(int v, int l, int r, int ql, int qr){ // превращаем все элементы с ql до qr в нули
if(qr < l || r < ql) return;
if(ql <= l && r <= qr){
tree[v] = 0;
return;
}
int mid = (l+r) >> 1;
update(v<<1, l, mid, ql, qr);
update((v<<1)+1, mid+1, r, ql, qr);
tree[v] = tree[v<<1] + tree[(v<<1)+1];
}
int get(int v, int l, int r, int k){ // находим k-ную единицу
if(l == r){
return l;
}
int mid = (l+r) >> 1;
if(k <= tree[v<<1]){
return get(v<<1, l, mid, k);
}
else{
return get((v<<1)+1, mid+1, r, k-tree[v<<1]);
}
}
int quan(){
return tree[1];
}
} tree(MAXN);
bool cmp(pii a, pii b){
if(a.first == b.first) return a.second > b.second;
return a.first < b.first;
}
vector <pii> ranges;
vector <int> pref;
vector <vector <int>> graph(MAXN);
int sub[MAXN], pos[MAXN];
pii dfs(int u, int p = -1){
int mx = 0, in = ranges[u].first;
for(auto to : graph[u]){
if(to != p){
auto it = dfs(to, u);
if(it.first > mx){
mx = it.first;
in = it.second;
}
}
}
if(pref[ranges[u].second-1]-pref[ranges[u].first-1] == 0){
sub[u] = mx+1;
}
else{
sub[u] = mx;
}
pos[u] = in;
return mp(sub[u], pos[u]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
int i;
n = N;
for(i = 0; i < n-1; i++){
ranks[i+1] = K[i];
}
for(i = 0; i < C; i++){
s[i+1] = S[i]+1;
e[i+1] = E[i]+1;
}
tree.build(1, 1, n);
for(i = 1; i <= C; i++){
int s1 = tree.get(1, 1, n, s[i]);
if(tree.quan() < e[i]+1){
ranges.pb(mp(s1, n));
tree.update(1, 1, n, s1+1, n);
}
else{
int e1 = tree.get(1, 1, n, e[i]+1)-1;
ranges.pb(mp(s1, e1));
tree.update(1, 1, n, s1+1, e1);
}
}
sort(all(ranges), cmp);
pref.assign(n+1, 0);
for(i = 1; i < n; i++){
pref[i] += pref[i-1];
if(ranks[i] > R) pref[i]++;
}
for(i = 1; i < sz(ranges); i++){
int j = i-1;
while(!(ranges[j].first <= ranges[i].first && ranges[j].second >= ranges[i].second)) j--;
graph[i].pb(j);
graph[j].pb(i);
}
auto ans = dfs(0);
return --ans.second;
}
