#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 2e5+10;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
vector<int> tr[mxn];
int par[mxn][20],dep[mxn];
pii arr[mxn];
vector<pii> rng;
ordered_set<pii> st;
void dfs(int now){
//cerr<<"DFS: "<<arr[now].fs<<' '<<arr[now].sc<<' '<<dep[now]<<endl;
for(int i = 1;i<20;i++){
par[now][i] = par[par[now][i-1]][i-1];
}
for(auto nxt:tr[now]){
dep[nxt] = dep[now]+1;
par[nxt][0] = now;
dfs(nxt);
}
return;
}
int up(int now,int l,int r){
int lim = dep[now];
int ans = 0;
for(int i = 19;i>=0;i--){
int p = par[now][i];
if(arr[p].fs>l&&arr[p].sc<r){
now = p;
ans += 1<<i;
}
}
//cerr<<"UP: "<<now<<' '<<l<<' '<<r<<":"<<ans<<endl;
return min(ans,lim);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for(int i = 0;i<C;i++){
rng.push_back(pii(S[i],E[i]));
}
int ptr = N;
for(int i = 0;i<=N;i++)st.insert(pii(i,i)),arr[i] = pii(i,i);
for(auto &i:rng){
ptr++;
auto lit = st.find_by_order(i.fs);
auto rit = st.find_by_order(i.sc+1);
arr[ptr].fs = arr[lit->sc].fs;
arr[ptr].sc = arr[rit->sc].fs-1;
for(auto it = lit;it != rit;it++){
tr[ptr].push_back(it->sc);
}
//cerr<<i.fs<<' '<<i.sc<<":"<<arr[ptr].fs<<','<<arr[ptr].sc<<":"<<endl;
//for(auto &i:st)//cerr<<i.fs<<":"<<arr[i.sc].fs<<','<<arr[i.sc].sc<<' ';cerr<<endl;
int tmp = lit->fs;
auto it = lit;
while((it = st.find_by_order(i.fs))->fs<=arr[ptr].sc)st.erase(it);
st.insert(pii(tmp,ptr));
}
par[ptr][0] = ptr;
dfs(ptr);
std::priority_queue<int,vector<int>,greater<int>> pq;
pq.push(N);
for(int i = 0;i+1<N;i++){
if(K[i]>R)pq.push(i);
}
int pl = -1,pr = pq.top();
int ans = 0;
for(int i = 0;i<N;i++){
if(pq.top()<i){
pl = pq.top();
pq.pop();
}
pr = pq.top();
ans = max(ans,up(i,pl,pr+1));
}
return ans;
}
