#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'
struct FenwickTree{
vector<int> a; int n, s;
FenwickTree(int N){ a.resize((n=N)+1); }
void add(int i, int v){
for(++i; i<=n; i+=i&-i) a[i] += v;
}
int get(int i){
for(s=0; i>=1; i-=i&-i) s += a[i];
return s;
}
int get(int l, int r){ return get(r+1) - get(l); }
int lower(int v){
int i = 0;
for(s=1<<20; s; s/=2) if(i+s<=n && a[i+s]<v) v -= a[i+=s];
return i;
}
};
const int MAXN = 2e5;
struct SegmentTree{
vector<int> a; int sz = 1;
void init(vector<int> &v){
while(sz < (int)v.size()) sz += sz;
a.assign(2*sz, -1);
build(v, 0, 0, sz);
}
void build(vector<int> &v, int x, int lx, int rx){
if(rx-lx==1){
if(lx < (int)v.size()) a[x] = v[lx];
return;
}
int mx = (lx + rx) / 2;
build(v, 2*x+1, lx, mx);
build(v, 2*x+2, mx, rx);
a[x] = max(a[2*x+1], a[2*x+2]);
}
int rangeMax(int l, int r, int x, int lx, int rx){
if(r<=lx || rx<=l) return -1;
if(l<=lx && rx<=r) return a[x];
int mx = (lx + rx) / 2;
return max(rangeMax(l, r, 2*x+1, lx, mx), rangeMax(l, r, 2*x+2, mx, rx));
}
int rangeMax(int l, int r){ return rangeMax(l, r+1, 0, 0, sz); }
};
vector<int> g[MAXN];
int low[MAXN], high[MAXN], lim;
array<int, 2> dist[MAXN];
array<int, 2> ans = {0, 0};
SegmentTree st;
void dfs(int u){
if(g[u].empty()){
low[u] = high[u] = u;
dist[u] = {0, -u};
}else low[u] = MAXN * 3, high[u] = -1;
for(int v : g[u]){
dfs(v);
low[u] = min(low[u], low[v]);
high[u] = max(high[u], high[v]);
++dist[v][0];
dist[u] = max(dist[u], dist[v]);
}
int m = st.rangeMax(low[u], high[u] - 1);
if(m <= lim) ans = max(ans, dist[u]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
FenwickTree f(N);
lim = R;
for(int i=0; i<N; ++i) f.add(i, 1);
int a[N]; iota(a, a+N, 0LL);
int curr = N - 1;
for(int i=0; i<C; ++i){
++curr;
int l = f.lower(S[i] + 1), num = E[i] - S[i] + 1;
g[curr].push_back(a[l]);
a[l] = curr;
for(int j=1; j<num; ++j){
int k = f.lower(S[i] + 2);
g[curr].push_back(a[k]);
f.add(k, -1);
}
}
vector<int> v(N-1);
for(int i=0; i<N-1; ++i) v[i] = K[i];
st.init(v);
dfs(curr);
return -ans[1];
}
