#include <bits/stdc++.h>
using namespace std;
int lazy[2000000],node[1000000],mx[1000000],another[1000000],lazyanother[1000000];
void update(int id,int l,int r,int L,int R,int x){
if(lazy[id]!=-1){
node[id]=(lazy[id]*(r-l+1));
lazy[id*2]=lazy[id];
lazy[id*2+1]=lazy[id];
lazy[id]=-1;
}
if(r<L || R<l) return;
if(L<=l && r<=R){
node[id]=(x*(r-l+1));
lazy[id*2]=x;
lazy[id*2+1]=x;
return;
}
int m=l+r>>1;
update(id*2,l,m,L,R,x);
update(id*2+1,m+1,r,L,R,x);
node[id]=node[id*2]+node[id*2+1];
}
int query(int id,int l,int r,int x){
if(lazy[id]!=-1){
node[id]=(lazy[id]*(r-l+1));
int m=l+r>>1;
node[id*2]=lazy[id]*(m-l+1);
node[id*2+1]=lazy[id]*(r-m);
lazy[id*4]=lazy[id];
lazy[id*4+1]=lazy[id];
lazy[id*4+2]=lazy[id];
lazy[id*4+3]=lazy[id];
lazy[id]=-1;
}
if(l==r) return l;
int m=l+r>>1;
if(node[id*2]>=x) return query(id*2,l,m,x);
else return query(id*2+1,m+1,r,x-node[id*2]);
}
int rightt[100005];
void build(int id,int l,int r,int pos,int x){
if(l==r){
mx[id]=x;
return;
}
int m=l+r>>1;
if(m>=pos) build(id*2,l,m,pos,x);
else build(id*2+1,m+1,r,pos,x);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
int query1(int id,int l,int r,int L,int R){
if(r<L || R<l) return 0;
if(L<=l && r<=R) return mx[id];
int m=l+r>>1;
return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
void update1(int id,int l,int r,int L,int R){
another[id]+=(lazyanother[id]*(r-l+1));
lazyanother[id*2]+=lazyanother[id];
lazyanother[id*2+1]+=lazyanother[id];
lazyanother[id]=0;
if(r<L || R<l) return;
if(L<=l && r<=R){
another[id]+=(r-l+1);
lazyanother[id*2]++;
lazyanother[id*2+1]++;
return;
}
int m=l+r>>1;
update1(id*2,l,m,L,R);
update1(id*2+1,m+1,r,L,R);
another[id]=another[id*2]+another[id*2+1];
}
int query2(int id,int l,int r,int pos){
another[id]+=(lazyanother[id]*(r-l+1));
lazyanother[id*2]+=lazyanother[id];
lazyanother[id*2+1]+=lazyanother[id];
lazyanother[id]=0;
if(l==r) return another[id];
int m=l+r>>1;
if(m>=pos) return query2(id*2,l,m,pos);
else return query2(id*2+1,m+1,r,pos);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
memset(lazy,-1,sizeof(lazy));
for(int i=0;i<N;i++){
update(1,0,N-1,i,i,1);
rightt[i]=i;
}
for(int i=0;i<(N-1);i++){
build(1,0,N-1,i,K[i]);
}
// cout << node[1] << '\n';
for(int i=0;i<C;i++){
int x=query(1,0,N-1,S[i]+1);
int y=query(1,0,N-1,E[i]+1);
// cout << x << ' ' << y << '\n';
update(1,0,N-1,x+1,y,0);
rightt[x]=rightt[y];
// cout << x << ' ' << rightt[x] << '\n';
int lol=query1(1,0,N-1,x,rightt[y]-1);
// cout << lol << '\n';
if(R>lol) update1(1,0,N-1,x,rightt[x]);
}
pair<int,int>answer={0,-1000000000};
for(int i=0;i<N;i++){
answer=max(answer,{query2(1,0,N-1,i),-i});
}
return -answer.second;
}
