#include <stdio.h>
#include <set>
#include <algorithm>
#define ff first
#define ss second
#define pii pair<int,int>
#define ele 131072
using namespace std;
int n,c,r;
int k[111111],s[111111],e[111111];
int nxt[111111],idx[333333],res[111111];
void put_(int p,int num){
p+=ele; idx[p]=num;
for(p>>=1;p>1;p>>=1) idx[p]=max(idx[2*p],idx[2*p+1]);
}
int max_(int s,int e){
int mx=0;
s+=ele; e+=ele;
while(s<e){
if(s%2==1) mx=max(mx,idx[s++]);
if(e%2==0) mx=max(mx,idx[e--]);
s/=2; e/=2;
}
if(s==e) mx=max(mx,idx[s]);
return mx;
}
int GetBestPosition(int N,int C,int R,int *K,int *S,int *E){
n=N; c=C; r=R;
for(int i=0;i<N-1;i++) k[i]=K[i];
for(int i=0;i<C;i++) s[i]=S[i];
for(int i=0;i<C;i++) e[i]=E[i];
for(int i=0;i<n;i++) nxt[i]=i+1;
for(int i=0;i<n-1;i++) put_(i,k[i]);
for(int i=0;i<c;i++){
int bef=s[i],del=e[i]-s[i];
s[i]=0;
for(int j=0;j<bef;j++) s[i]=nxt[s[i]];
e[i]=s[i];
for(int j=0;j<=del;j++) e[i]=nxt[e[i]];
nxt[s[i]]=e[i]; e[i]--;
}
/*
for(int i=0;i<c;i++) printf("%d %d\n",s[i],e[i]);
printf("\n");
*/
for(int i=0;i<c;i++){
if(r>max_(s[i],e[i]-1)){
res[s[i]]++;
res[e[i]+1]--;
}
}
int mx=0,sum=0;
for(int i=0;i<n;i++) sum+=res[i],mx=max(mx,sum);
return mx;
}
