#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
using namespace std;
typedef vector <int> VI;
typedef vector <VI> VVI;
struct Fenwick {
VI aib;
int n;
inline void init(int _n) {
n = _n;
aib.resize(n + 1);
}
inline void clr() {
fill(aib.begin(), aib.end(), 0);
}
inline void update(int pos, int val) {
for(int i = pos; i <= n; i += lsb(i)) {
aib[i] += val;
}
}
inline int query(int pos) {
int ans = 0;
for(int i = pos; i > 0; i -= lsb(i)) {
ans += aib[i];
}
return ans;
}
inline int sum(int l, int r) {
return query(r) - query(l - 1);
}
inline int kth(int k) {
int res = 0, cnt = 0;
for(int step = 1 << 17; step; step >>= 1) {
if(res + step <= n && cnt + aib[res + step] < k) {
res += step;
cnt += aib[res];
}
}
return res + 1;
}
};
void dfs(int nod, VVI &g, VI &idl, VI &idr, VI &lvl, int n) {
idl[nod] = n + 1, idr[nod] = 0;
for(auto it : g[nod]) {
lvl[it] = lvl[nod] + 1;
dfs(it, g, idl, idr, lvl, n);
idl[nod] = min(idl[nod], idl[it]), idr[nod] = max(idr[nod], idr[it]);
}
if(nod <= n) {
idl[nod] = idr[nod] = nod;
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
Fenwick fen; fen.init(N);
for(int i = 1; i <= N; i++) {
fen.update(i, 1);
}
VVI g(N + C + 1); VI id(N + 1);
iota(id.begin(), id.end(), 0);
VVI anc(N + C + 1, VI(18));
int cur = N;
for(int i = 0; i < C; i++) {
S[i]++, E[i]++, cur++;
int aux = fen.kth(S[i]);
for(int j = S[i]; j <= E[i]; j++) {
int pos = fen.kth(S[i]);
fen.update(pos, -1);
g[cur].push_back(id[pos]);
anc[id[pos]][0] = cur;
}
fen.update(aux, 1);
id[aux] = cur;
}
for(int bit = 1; (1 << bit) <= cur; bit++) {
for(int i = 1; i <= cur; i++) {
anc[i][bit] = anc[anc[i][bit - 1]][bit - 1];
}
}
VI idl(cur + 1), idr(cur + 1), lvl(cur + 1);
dfs(cur, g, idl, idr, lvl, N);
fen.clr();
for(int i = 2; i <= N; i++) {
fen.update(i, (K[i - 2] > R));
}
int ans, mx = -1;
for(int i = 1; i <= N; i++) {
int nod = i;
for(int bit = 17; bit >= 0; bit--) {
int cur = anc[nod][bit];
if(cur > 0 && fen.sum(idl[cur], idr[cur]) == 0) {
nod = cur;
}
}
if(mx < lvl[i] - lvl[nod]) {
mx = lvl[i] - lvl[nod], ans = i;
}
if(i < N) {
if(K[i - 1] > R) {
fen.update(i + 1, -1);
fen.update(i, 1);
}
else {
fen.update(i + 1, 1);
fen.update(i, -1);
}
}
}
return ans - 1;
}
