#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,lg=18;
int all[maxn],n,c,r,kaf=(1<<lg);
struct segment{
struct node{
int mina,maxa;
int lazy,lazygozash;
node(){
lazy=0;
lazygozash=-1;
}
};
node seg[(1<<(lg+1))];
segment(){
for(int i=(1<<(lg+1))-1;i>=0;i--){
if(i>=kaf){
seg[i].maxa=seg[i].mina=i-kaf;
}else{
seg[i].maxa=max(seg[(i<<1)].maxa,seg[(i<<1)^1].maxa);
seg[i].mina=min(seg[(i<<1)].mina,seg[(i<<1)^1].mina);
}
}
}
void calc(int i){
if(i>=kaf){
if(seg[i].lazygozash!=-1){
seg[i].mina=seg[i].maxa=seg[i].lazygozash;
seg[i].lazygozash=-1;
}
seg[i].mina+=seg[i].lazy;
seg[i].maxa+=seg[i].lazy;
seg[i].lazy=0;
return ;
}
int mnav,mndov,mxav,mxdov;
if(seg[(i<<1)].lazygozash==-1){
mnav=seg[(i<<1)].mina;
mxav=seg[(i<<1)].maxa;
}else{
mnav=seg[(i<<1)].lazygozash;
mxav=seg[(i<<1)].lazygozash;
}
mnav+=seg[(i<<1)].lazy;
mxav+=seg[(i<<1)].lazy;
if(seg[(i<<1)^1].lazygozash==-1){
mndov=seg[(i<<1)^1].mina;
mxdov=seg[(i<<1)^1].maxa;
}else{
mndov=seg[(i<<1)^1].lazygozash;
mxdov=seg[(i<<1)^1].lazygozash;
}
mndov+=seg[(i<<1)^1].lazy;
mxdov+=seg[(i<<1)^1].lazy;
seg[i].mina=min(mnav,mndov);
seg[i].maxa=max(mxav,mxdov);
}
void shift(int i){
if(i>=kaf){
return ;
}
if(seg[i].lazygozash!=-1){
seg[(i<<1)].lazygozash=seg[i].lazygozash;
seg[(i<<1)^1].lazygozash=seg[i].lazygozash;
seg[i].lazygozash=-1;
seg[(i<<1)].lazy=seg[(i<<1)^1].lazy=0;
}
seg[(i<<1)].lazy+=seg[i].lazy;
seg[(i<<1)^1].lazy+=seg[i].lazy;
seg[i].lazy=0;
}
void ins(int i,int l,int r,int tl,int tr,int w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
shift(i);
calc(i);
seg[i].lazygozash=w;
shift(i);
calc(i);
return ;
}
int m=(l+r)>>1;
shift(i);
ins((i<<1),l,m,tl,tr,w);
ins((i<<1)^1,m+1,r,tl,tr,w);
calc(i);
return ;
}
void upd(int i,int l,int r,int tl,int tr,int w){
if(l>r||l>tr||r<tl|tl>tr){
return ;
}
if(l>=tl&&r<=tr){
shift(i);
calc(i);
seg[i].lazy+=w;
shift(i);
calc(i);
return ;
}
int m=(l+r)>>1;
shift(i);
upd((i<<1),l,m,tl,tr,w);
upd((i<<1)^1,m+1,r,tl,tr,w);
calc(i);
return ;
}
int pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
shift(i);
calc(i);
if(l>=tl&&r<=tr){
return seg[i].mina;
}
int m=(l+r)>>1;
return pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
}
int findakh(int i,int l,int r,int tl,int tr,int w){
shift(i);
calc(i);
if(l>r||l>tr||r<tl||tl>tr||seg[i].mina>w){
return -1;
}
if(l==r){
return l;
}
int m=(l+r)>>1;
int ret=findakh((i<<1)^1,m+1,r,tl,tr,w);
if(ret==-1){
ret=findakh((i<<1),l,m,tl,tr,w);
}
return ret;
}
int findav(int i,int l,int r,int tl,int tr,int w){
shift(i);
calc(i);
if(l>r||l>tr||r<tl||tl>tr||seg[i].maxa<w){
return -1;
}
if(l==r){
return l;
}
int m=(l+r)>>1;
int ret=findav((i<<1),l,m,tl,tr,w);
if(ret==-1){
ret=findav((i<<1)^1,m+1,r,tl,tr,w);
}
return ret;
}
}seg1,seg2;
vector<pair<int,int>>alle;
int last[maxn];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
n=N;
c=C;
r=R;
int ls=-1;
for(int i=0;i<n-1;i++){
all[i]=K[i];
if(all[i]>r){
ls=i;
}
last[i]=ls;
}
alle.resize(c);
for(int i=0;i<c;i++){
alle[i]=make_pair(S[i],E[i]);
alle[i].first=seg1.findav(1,0,kaf-1,0,n-1,alle[i].first);
alle[i].second=seg1.findakh(1,0,kaf-1,0,n-1,alle[i].second);
if(last[alle[i].second-1]<alle[i].first){
seg2.upd(1,0,kaf-1,alle[i].first,alle[i].second,1);
}
seg1.ins(1,0,kaf-1,alle[i].first,alle[i].second,S[i]);
seg1.upd(1,0,kaf-1,alle[i].second+1,n,-E[i]+S[i]);
// cout<<i<<" "<<alle[i].first<<" "<<alle[i].second<<endl;
// for(int i=0;i<n;i++){
// cout<<seg1.pors(1,0,kaf-1,i,i)<<" ";
// }
// cout<<"\n";
}
pair<int,int>res;
res=make_pair(-1,1);
for(int i=0;i<n;i++){
res=max(res,make_pair(seg2.pors(1,0,kaf-1,i,i)-i,-i));
}
return -res.second;
}
