#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
struct FenwickTree {
Vec<int> data;
FenwickTree(const int n): data(n + 1) {}
void add(int i, const int x) {
i += 1;
while (i < (int) data.size()) {
data[i] += x;
i += i & -i;
}
}
int get(int i) const {
int ret = 0;
while (i > 0) {
ret += data[i];
i -= i & -i;
}
return ret;
}
int fold(const int l, const int r) const {
return get(r) - get(l);
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
if (R == N - 1) return 0;
FenwickTree fen(N);
const auto get_kth = [&](const int k) {
int ok = -1, ng = N;
while (ng - ok > 1) {
const auto md = (ok + ng) / 2;
(fen.fold(0, md) <= k ? ok : ng) = md;
}
return ok;
};
const int V = N + C;
Vec<int> max(V, -1);
Vec<int> belong(N);
for (int i = 0; i < N; ++i) {
fen.add(i, 1);
belong[i] = i;
}
std::array<Vec<int>, 20> par;
par[0] = Vec<int>(V);
for (int i = 0; i < C; ++i) {
const int u = N + i;
for (int j = S[i]; j <= E[i]; ++j) {
const auto k = get_kth(S[i]);
const auto v = belong[k];
par[0][v] = u;
max[u] = std::max(max[u], max[v]);
if (j == E[i]) {
belong[k] = u;
}
else {
max[u] = std::max(max[u], K[k]);
fen.add(k, -1);
}
}
}
par[0][N + C - 1] = N + C - 1;
for (int i = 1; i < 20; ++i) {
par[i] = Vec<int>(V);
for (int j = 0; j < V; ++j) {
par[i][j] = par[i - 1][par[i - 1][j]];
}
}
int ret = -1, val = -1;
for (int i = 0; i < N; ++i) {
int len = 0;
int u = i;
for (int j = 19; j >= 0; --j) {
const auto v = par[j][u];
if (max[v] < R) {
u = v;
len += 1 << j;
}
}
if (val < len) {
val = len;
ret = i;
}
}
return ret;
}
