#include <bits/stdc++.h>
int bit[100001], nodeat[100001];
void update(int pos, int val, int N) {
for (; pos <= N; pos += (pos & (-pos))) bit[pos] += val;
}
int query(int pos, int N) {
int ans = 0;
for (; pos > 0; pos -= (pos & (-pos))) ans += bit[pos];
return ans;
}
int binsearch(int val, int N) {
int l = 1, r = N;
while (l != r) {
int mid = (l + r) / 2;
if (query(mid, N) < val)
l = mid + 1;
else
r = mid;
}
return l;
}
std::vector<int> graph[200001];
int colour[200001], knights[100001];
std::pair<int, int> maxwins[200001];
int ans_wins = -1, ans_node = 0;
// 0 = All W, 1 = Leftmost B; everthing else W, 2 = B somewhere else
void dfs(int node) {
if (graph[node].empty()) {
colour[node] = knights[node];
maxwins[node] = {0, node};
} else {
for (int i : graph[node]) {
dfs(i);
if (colour[i] && i != graph[node].back()) colour[node] = 2;
}
if (colour[node] != 2) {
if (colour[graph[node].back()])
colour[node] = 1;
else
colour[node] = 0;
}
if (colour[node] == 0) {
int wins = -1, best = 0;
for (int i = graph[node].size() - 1; ~i; i--) {
if (maxwins[graph[node][i]].first + 1 > wins)
wins = maxwins[graph[node][i]].first + 1, best = maxwins[graph[node][i]].second;
}
maxwins[node] = {wins, best};
} else if (colour[node] == 1) {
maxwins[node] = maxwins[graph[node].back()];
maxwins[node].first++;
} else
maxwins[node] = maxwins[graph[node].back()];
}
// std::cout << node << ' ' << colour[node] << ' ' << maxwins[node].first
// << ' ' << maxwins[node].second << '\n';
if (maxwins[node].first > ans_wins)
ans_wins = maxwins[node].first, ans_node = maxwins[node].second;
else if (maxwins[node].first == ans_wins)
ans_node = std::min(ans_node, maxwins[node].second);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for (int i = 1; i <= N; i++) {
update(i, 1, N);
nodeat[i] = i;
}
int indx = N + 1;
for (int i = 0; i < C; i++) {
S[i]++, E[i]++;
for (int j = E[i]; j > S[i]; j--) {
int pos = binsearch(j, N);
graph[indx].push_back(nodeat[pos]);
update(pos, -1, N);
}
int pos = binsearch(S[i], N);
graph[indx].push_back(nodeat[pos]);
nodeat[pos] = indx++;
}
knights[1] = 0;
for (int i = 0; i < N - 1; i++) knights[i + 2] = (K[i] > R);
dfs(indx - 1);
// std::cout << ans_wins << '\n';
return ans_node - 1;
}
