#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int NN=100000;
int tree[4*NN];
void in_updt(int node, int l, int r){
int m = (l + r)/2;
if (l == r){
tree[node]=1;
return;
}
in_updt(node*2, l, m);
in_updt(node*2 + 1, m+1, r);
tree[node] = tree[node*2]+tree[node*2+1];
}
void update(int node, int l, int r, int x, int y){
int m = (l + r)/2;
if (l>y || r<=x || tree[node]==0)return;
if (l >x && r<=y ){
tree[node]=0;
return;
}
update(node*2, l, m, x, y );
update(node*2 + 1, m+1, r, x, y );
tree[node] = tree[node*2]+tree[node*2+1];
}
pair<int,int> query(int node, int l, int r, int x, int y, bool lx, bool ly){
int m = (l + r)/2;
if (l==r)return {l,r};
if (lx && ly){
if (tree[node*2]>=y)return query(node*2,l,m,x,y,1,1);
if (tree[node*2]<x)return query(node*2+1, m+1, r, x-tree[node*2],y-tree[node*2],1,1);
return {query(node*2,l,m,x,0,1,0).first,query(node*2+1, m+1, r, 0,y-tree[node*2],0,1).second };
}else if (lx){
if (tree[node*2]>x)return query(node*2+1,m+1,r,x-tree[node*2],0,1,0);
return query(node*2,l,m,x,0,1,0);
}else if (ly){
if (tree[node*2]>=y)return query(node*2,l,m,0,y,0,1);
else return query(node*2+1, m+1,r, 0, y-tree[node*2],0,1);
}else return {-1,-1};
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
memset(tree, 0, sizeof tree);
in_updt(1,0,N-1);
int mayores[N+10];
int c=0;
mayores[0]=0;
for (int i = 1 ; i < N;++i){
if (K[i-1]>R)c++;
mayores[i]=c;
//cout<<c<<" ";
}
mayores[N]=c;
mayores[N+1]=c;
//cout<<endl;
//
//if (1) return 0;
//
int zipline[N+10];
memset(zipline, 0, sizeof zipline);
for (int i = 0 ; i < C; ++i){
pair<int,int> range = query(1,0,N-1,S[i],E[i],1,1);
//cout<<S[i]<<" "<<E[i]<<" -> "<<range.first<<" "<<range.second<<" ->";
if (mayores[range.first] == mayores[range.second]){
zipline[range.first]+=1;
zipline[range.second+1]-=1;
//cout<<"[AC]";
}//else cout<<"[WA]";
//cout<<endl;
update(1,0,N-1,range.first,range.second);
//for (int i = 1; i < 20;++i)cout<<tree[i]<<" ";
//cout<<endl;
}
c=0;
int maxx=0;
int maxxwho=0;
for (int i = 0 ; i < N;++i){
c+=zipline[i];
//cout<<c<<" ";
if (c>maxx){
maxx=c;
maxxwho=i;
}
}
//cout<<endl;
return maxxwho;
}
