#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;
#define REP(a,b,c) for(int a=b;a<c;a++)
#define S second
#define F first
#define LSOne(s) ((s)&(-s))
#define PB push_back
#define all(x) (x).begin(),(x).end()
vi ft;
int n;
void update(int x,int v){
x++;
while(x<=n){
ft[x]+=v;
x+=LSOne(x);
}
}
int query(int x){
x++;
int ans=0;
while(x){
ans+=ft[x];
x-=LSOne(x);
}
return ans;
}
int solve(int x){
int l=0,r=n-1;
while(l!=r){
int m=(l+r)/2;
if(query(m)>=x+1)r=m;
else l=m+1;
}
return l;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n=N;
ft.resize(n+1,0);
REP(i,0,n)update(i,1);
vector<pi> a(n),b;
REP(i,0,n)a[i]={i,i};
set<int> st;
REP(i,0,n)st.insert(i);
int k=log2(n)+1;
vii mx(n,vi(k));
REP(i,0,n)mx[i][0]=K[i];
REP(j,1,k)REP(i,0,n)if(i+(1<<(j-1))<n)mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
REP(i,0,C){
int x=solve(S[i]),y=solve(E[i]);
x=a[x].F;y=a[y].S;
a[y]={x,y};
int z=y-x,lg=log2(z);
if(max(mx[x][lg],mx[y-(1<<lg)][lg])<R)b.PB({x,y});
auto it=st.lower_bound(x);
while(it!=st.end()&&*it<y){
update(*it,-1);
st.erase(it);
it=st.lower_bound(x);
}
}
sort(all(b));
vi ans(n,0);
int pos=0,cnt=0;
priority_queue<int,vi,greater<int>> pq;
REP(i,0,n){
if(pos<C&&b[pos].F<=i){
pq.push(b[pos].S);
pos++;cnt++;
}
while(!pq.empty()&&pq.top()<i){
pq.pop();
cnt--;
}
ans[i]=cnt;
}
return *max_element(all(ans));
}
