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