#include <bits/stdc++.h>
using namespace std;
const int N=100006;
struct node{
int cnt;
int maximum,noRight;
int height;
int index;
} sg[4*N];
node operator +(const node a,const node b){
if (a.height==-1) return b;
if (b.height==-1) return a;
node c;
c.cnt=a.cnt+b.cnt;
c.maximum=max(a.maximum,b.maximum);
c.noRight=max(a.maximum,b.noRight);
if (a.height>=b.height){
c.height=a.height;
c.index=a.index;
}
else{
c.height=b.height;
c.index=b.index;
}
return c;
}
void build (int v,int tl,int tr,int arr[]){
if (tl==tr){
sg[v].cnt=1;
sg[v].noRight=0;
sg[v].maximum=arr[tl];
sg[v].height=1;
sg[v].index=tl;
return;
}
int tm=(tl+tr)/2;
build(v+v,tl,tm,arr);
build(v+v+1,tm+1,tr,arr);
sg[v]=sg[v+v]+sg[v+v+1];
}
void del(int v,int tl,int tr,int l,int r){
if (l>r) return;
if (l==1 && r==sg[v].cnt){
sg[v].cnt=0;
sg[v].maximum=sg[v].noRight=0;
sg[v].height=-1;
return;
}
int border=sg[v+v].cnt,tm=(tl+tr)/2;
del(v+v,tl,tm,l,min(border,r));
del(v+v+1,tm+1,tr,max(border+1,l)-border,r-border);
sg[v]=sg[v+v]+sg[v+v+1];
}
void update (int v,int tl,int tr,int ind,node newNode){
if (sg[v].cnt==1){
sg[v].maximum=newNode.maximum;
sg[v].noRight=newNode.noRight;
sg[v].height=newNode.height;
sg[v].index=newNode.index;
return;
}
int border=sg[v+v].cnt,tm=(tl+tr)/2;
if (ind<=border)
update(v+v,tl,tm,ind,newNode);
else
update(v+v+1,tm+1,tr,ind-border,newNode);
sg[v]=sg[v+v]+sg[v+v+1];
}
node query(int v,int tl,int tr,int l,int r){
//cout<<sg[v].cnt<<endl;
if (l>r) return {0,0,0,-1,-1};
if (l==1 && r==sg[v].cnt){
//cout<<sg[v].maximum<<" "<<sg[v].noRight<<endl;
return sg[v];
}
int border=sg[v+v].cnt,tm=(tl+tr)/2;
node left=query(v+v,tl,tm,l,min(border,r));
node right=query(v+v+1,tm+1,tr,max(border+1,l)-border,r-border);
//cout<<left.maximum<<" "<<left.noRight<<" "<<left.index<<" "<<right.maximum<<" "<<right.noRight<<" "<<right.index<<endl;
return left+right;
}
int GetBestPosition(int n, int q, int addVal, int rank[], int start[], int end[]) {
pair<int,int> finalAns={-1,0};
if (n==1) return 0;
for (int i=0;i<n-1;i++){
rank[i]++;
}
rank[n-1]=0;
//cout<<rank[n-1]<<endl;
build(1,0,n-1,rank);
for (int i=0;i<q;i++){
node ans=query(1,0,n-1,start[i]+1,end[i]+1);
del(1,0,n-1,start[i]+2,end[i]+1);
//cout<<ans.maximum<<" "<<ans.noRight<<" "<<ans.height<<" "<<ans.index<<endl<<endl;
ans.height++;
if (ans.noRight<=addVal)
finalAns=max(finalAns,{ans.height,ans.index});
update(1,0,n-1,start[i]+1,ans);
}
return finalAns.second;
}
