const int Z = 1 << 17;
int next[Z],cnt[Z*2];
int getnth(int n)
{
int x = 1;
while (x < Z){
x <<= 1;
if (cnt[x] < n) n -= cnt[x++];
}
return x - Z;
}
void up(int x, int p)
{
x += Z;
while (x){
cnt[x] += p;
x >>= 1;
}
}
int add[Z],res[Z];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int i,peo,x,y;
for (i=0;i<N;i++) next[i] = i+1, cnt[i+Z] = 1;
for (i=Z-1;i>=1;i--) cnt[i] = cnt[i*2] + cnt[i*2+1];
for (i=0;i<C;i++){
peo = E[i] - S[i];
S[i] = getnth(S[i]+1);
x = next[S[i]];
while (peo--){
up(x,-1);
x = next[x];
}
E[i] = x - 1;
next[S[i]] = x;
}
for (i=1;i<N;i++) add[i] = add[i-1] + (K[i-1] > R);
for (i=0;i<C;i++){
if (add[E[i]] == add[S[i]]){
res[S[i]]++;
res[E[i]]--;
}
}
int s = 0, p = -1, ind;
for (i=0;i<N;i++){
s += res[i];
if (p < s){
p = s;
ind = i;
}
}
return ind;
}
