#include<iostream>
#include<vector>
using namespace std;
vector<int> nei[3000000];
int n,c,r;
int arr [3000000];
int ansL[3000000];
int ansR[3000000];
int maxchain[3000000];
int index[3000000];
class FT{
private:vector<int> ft;
public: FT(int n){ft.assign(n+1,0);}
int rsq(int b){
int ans=0;
for(;b;b-=(b&(-b)))ans+=ft[b];
return ans;
}
void update(int k, int v){
for(;k<(int)ft.size();k+=(k&(-k)))ft[k]+=v;
}
};
int DPl(int node){
if(node==n-1){
ansL[node]=0;
return 0;
}
if(node<n-1){
ansL[node]=arr[node];
return arr[node];
}
ansL[node]=n;
for(int i=0;i<(int)nei[node].size();i++){
int v=nei[node][i];
ansL[node]=min(ansL[node],DPl(v));
}
return ansL[node];
}
int DPr(int node){
if(node==0){
ansR[node]=0;
return 0;
}
if(node<n){
ansR[node]=arr[node-1];
return arr[node-1];
}
ansR[node]=n;
for(int i=0;i<(int)nei[node].size();i++){
int v=nei[node][i];
ansR[node]=min(ansR[node],DPr(v));
}
return ansR[node];
}
int ChainDP(int node){
if(maxchain[node]!=-1){
return maxchain[node];
}
if(node<n){
index[node]=-1;
maxchain[node]=0;
return 0;
}
int ans=0;
int DPright[nei[node].size()];
int DPleft[nei[node].size()];
DPleft[0]=n+1;
for(int i=0;i<(int)nei[node].size()-1;i++){
int v=nei[node][i];
DPleft[i+1]=min(DPleft[i],DPl(v));
}
DPright[nei[node].size()-1]=n+1;
for(int i=nei[node].size()-1;i>0;i--){
int v=nei[node][i];
DPright[i-1]=min(DPright[i],DPr(v));
}
index[node]=-1;
for(int i=0;i<(int)nei[node].size();i++){
if(min(r,DPleft[i])==r && min(r,DPright[i])==r && ans<1+ChainDP(nei[node][i])){
ans=max(ans,1+ChainDP(nei[node][i]));
index[node]=nei[node][i];
}
}
if(ans==0)ans=-1;
maxchain[node]=ans;
return ans;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n=N;
c=C;
r=R;
r=n-r;
for(int i=0;i<n-1;i++){
arr[i]=K[i];
arr[i]=n-arr[i];
}
int counter=n;
int pointer[n];
int next[n];
for(int i=0;i<n;i++){
pointer[i]=i;
next[i]=i+1;
}
FT a(n);
for(int i=0;i<c;i++){
int x,y;
x=S[i];
y=E[i];
int hi,lo;
lo=-1;
hi=n;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(a.rsq(mid+1)+mid<x)lo=mid;
else hi=mid;
}
int start=hi;
nei[counter].push_back(pointer[hi]);
while(y>x){
hi=next[hi];
a.update(hi+1,-1);
y--;
nei[counter].push_back(pointer[hi]);
}
hi=next[hi];
next[start]=hi;
pointer[start]=counter;
counter++;
}
DPl(n+c-1);
DPr(n+c-1);
for(int i=0;i<n+c;i++)maxchain[i]=-1;
for(int i=0;i<n+c;i++)ChainDP(i);
int maximo=0;
for(int i=0;i<n+c;i++){
if(maxchain[maximo]<maxchain[i])maximo=i;
}
while(index[maximo]!=-1){
maximo=index[maximo];
}
return maximo;
}
