#include <bits/stdc++.h>
using namespace std;
#define BIG 100003
int fen[BIG], in[BIG], p[BIG], last[BIG], ans[BIG], N;
int find(int v){
return in[v] == 1 ? v : p[v] = find(p[v]);
}
inline void upd(int loc){
while(loc < BIG){
fen[loc]--;
loc += loc & -loc;
}
}
inline void rangeupd(int l, int r){
while((l = find(p[l])) <= r){
in[l] = 0;
upd(l);
}
}
inline int finder(int val){
int res = 0;
int id = 0;
for(int i = 16; i >= 0; i--){
if(id + (1 << i) <= N && res + fen[id + (1 << i)] < val){
id += 1 << i;
res += fen[id];
}
}
return id+1;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int i;
::N = N;
for(i = 1; i <= N; i++)
p[i] = i + 1;
for(i = 1; i < BIG; i++){
fen[i] = i & -i;
in[i] = 1;
}
for(i = 1; i < N; i++){
if(K[i - 1] > R) last[i] = i;
else last[i] = last[i - 1];
}
last[N] = last[N - 1];
for(i = 0; i < C; i++){
S[i] = finder(S[i] + 1);
E[i] = find(p[finder(E[i] + 1)]) - 1;
rangeupd(S[i], E[i]);
if(last[E[i] - 1] < S[i]){
ans[S[i]]++;
ans[E[i] + 1]--;
}
}
int ret = 1;
for(i = 1; i < BIG; i++){
ans[i] += ans[i - 1];
if(ans[i] > ans[ret]) ret = i;
}
return ret - 1;
}
