#include <bits/stdc++.h>
using namespace std;
const int MAX=1e5+5;
const int LOG=20;
int ub(int x){
return x&(-x);
}
struct AIB{
int n;
int v[MAX];
void add(int pos,int val){
while(pos<=n){
v[pos]+=val;
pos+=ub(pos);
}
}
int sum(int pos){
int s=0;
while(pos){
s+=v[pos];
pos-=ub(pos);
}
return s;
}
int bin_search(int sum){
int poz=0,s=0;
int i;
for(i=LOG-1;i>=0;--i)
if(poz+(1<<i)<=n && s+v[poz+(1<<i)]<sum){
poz+=(1<<i);
s+=v[poz];
}
return poz+1;
}
}aibSet,aibSum;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
aibSet.n=N;
aibSum.n=N;
int i,j;
for(i=1;i<=N;++i)
aibSet.add(i,1);
vector<int>ult(N-1);
if(K[0]<R)
ult[0]=0;
else
ult[0]=1;
for(i=1;i<N-1;++i)
if(K[i]<R)
ult[i]=ult[i-1];
else
ult[i]=i+1;
for(i=0;i<C;++i){
++S[i];
++E[i];
for(j=S[i]+1;j<=E[i];++j){
int pos=aibSet.bin_search(S[i]+1);
aibSet.add(pos,-1);
}
int pos1=aibSet.bin_search(S[i]);
int pos2=aibSet.bin_search(S[i]+1);
if(ult[pos2-3]<=pos1-1){
aibSum.add(pos1,1);
aibSum.add(pos2,-1);
}
}
int poz=0,best=-1;
for(i=0;i<N;++i){
int val=aibSum.sum(i+1);
if(val>best){
poz=i;
best=val;
}
}
return poz;
}
