#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 == r && 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){
int m = (l + r)/2;
if (l==r || (x<0 && y>NN ))return {l,r};
if (0==x)return {l,query(node,l,r,(2*NN)*-1,y).second};
if (tree[node]==y)return {query(node,l,r,x,2*NN).first,r};
if (tree[node*2]==x)return {m+1,query(node*2+1,m+1,r,x-tree[node*2],y-tree[node*2]).second};
if (tree[node*2] > y)return query(node*2,l,m,x,y);
if (tree[node*2]<=x)return query(node*2+1,m+1,r,x-tree[node*2],y-tree[node*2]);
return {query(node*2,l,m,x,2*NN).first, query(node*2+1,m+1,r,(2*NN)*-1,y-tree[node*2]).second };
}
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]);
//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;
}
