#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e5+5;
int up[MXN][20];
int t[MXN*4];
int lazy[MXN*4];
int k[MXN];
int p[MXN];
void apply(int node, int val, int l, int r) {
t[node] = val * (r - l + 1);
lazy[node] = val;
}
void push(int node, int l, int r) {
if (lazy[node] != -1) {
int mid = (l + r) >> 1;
apply(node << 1, lazy[node], l, mid);
apply(node << 1 | 1, lazy[node], mid + 1, r);
lazy[node] = -1;
}
}
void update(int node, int l, int r, int L, int R, int val) {
if (l > R || r < L) return;
if (l >= L && r <= R) {
apply(node, val, l, r);
return;
}
push(node, l, r);
int mid = (l + r) >> 1;
update(node << 1, l, mid, L, R, val);
update(node << 1 | 1, mid + 1, r, L, R, val);
t[node] = t[node << 1] + t[node << 1 | 1];
}
int get_pos(int node, int l, int r, int val) {
if (l == r) return l;
push(node, l, r);
int mid = (l + r) >> 1;
if (t[node << 1] >= val) return get_pos(node << 1, l, mid, val);
return get_pos(node << 1 | 1, mid + 1, r, val - t[node << 1]);
}
int merge(int x, int y) {
if (k[x] > k[y]) return x;
return y;
}
int getmax(int l, int r) {
if (l > r) return -1;
int lg = 31 - __builtin_clz(r - l + 1);
return merge(up[l][lg], up[r - (1 << lg) + 1][lg]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for (int i = 0; i <= N + 2; i++) {
p[i] = 0;
if (i < 4 * MXN) { t[i] = 0; lazy[i] = -1; }
}
for (int i = 0; i < N - 1; i++) {
k[i] = K[i];
up[i][0] = i;
}
for (int j = 1; j < 20; j++) {
for (int i = 0; i + (1 << j) <= N - 1; i++) {
up[i][j] = merge(up[i][j - 1], up[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 1; i <= N; i++) {
update(1, 1, N, i, i, 1);
}
for (int i = 0; i < C; i++) {
int l_orig = get_pos(1, 1, N, S[i] + 1);
int r_orig = get_pos(1, 1, N, E[i] + 1);
int mx_enemy = -1;
if (l_orig < r_orig) {
int best_idx = getmax(l_orig - 1, r_orig - 2);
if (best_idx != -1) mx_enemy = k[best_idx];
}
if (R > mx_enemy) {
p[l_orig]++;
p[r_orig + 1]--;
}
if (l_orig < r_orig) {
update(1, 1, N, l_orig + 1, r_orig, 0);
}
}
int max_wins = -1, best_pos = 1, cur_wins = 0;
for (int i = 1; i <= N; i++) {
cur_wins += p[i];
if (cur_wins > max_wins) {
max_wins = cur_wins;
best_pos = i;
}
}
return best_pos - 1;
}
