#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],l,r,z,k,za,seg[400009],cnt,msh[200009][20],PI,lst[200009],MX[200009],pas,ANS,val,fx[200009];
vector <int> v[200009];
pair <int, int> P[200009];
set <int> s;
set <int>::iterator it,tt;
void read(int q, int w, int rr){
if(q==w){
z=q;
return;
}
if(seg[rr*2]>=k){
read(q,(q+w)/2,rr*2);
}else{
k-=seg[rr*2];
read((q+w)/2+1,w,rr*2+1);
}
}
void upd(int q, int w){
seg[za+q-1]=w;
q=(za+q-1)/2;
while(q){
seg[q]=seg[q*2]+seg[q*2+1];
q>>=1;
}
}
void dfsst(int q, int w){
msh[q][0]=w;
for(int h=1; h<=18; h++){
msh[q][h]=msh[msh[q][h-1]][h-1];
}
if(q<=a){
lst[q]=q;
return;
}
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
dfsst((*it),q);
}
for(int h=0; h<v[q].size(); h++){
if(h+1==v[q].size()){
lst[q]=lst[v[q][h]];
MX[q]=max(MX[q],MX[v[q][h]]);
}else{
MX[q]=max(MX[q],MX[v[q][h]]);
MX[q]=max(MX[q],f[lst[v[q][h]]]);
}
}
}
int GetBestPosition(int NN, int CC, int RR, int *KK, int *SS, int *EE) {
a=NN;val=RR;
for(i=1; i<a; i++){
f[i]=KK[i-1];
}
PI=0;
for(ii=0; ii<CC; ii++){
PI++;P[PI]={SS[ii]+1,EE[ii]+1};
}
za=1;
while(za<a) za*=2;
for(i=1; i<=a; i++){
s.insert(i);fx[i]=i;
}
for(i=1; i<=a; i++){
seg[za+i-1]=1;
}
for(i=za-1; i>=1; i--){
seg[i]=seg[i*2]+seg[i*2+1];
}
cnt=a;
for(ii=1; ii<=PI; ii++){
z=0;k=P[ii].first;
read(1,za,1);
it=s.lower_bound(z);e=P[ii].second-P[ii].first+1;
xc=(*it);
cnt++;
while(e){
e--;
upd((*it),0);
v[cnt].push_back(fx[(*it)]);
tt=it;tt++;
s.erase(it);
it=tt;
}
s.insert(xc);
upd(xc,1);
fx[xc]=cnt;
}
dfsst(cnt,0);
ANS=0;
for(i=1; i<=a; i++){
pas=0;
c=i;c=msh[c][0];
while(c){
if(MX[c]>val) break;
pas++;c=msh[c][0];
}
ANS=max(ANS,pas);
}
return ANS;
}
