#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 100010, LG = 17;
int mx[LG][MAX_N];
// [L, R)
int qry(int l, int r) {
int lg = __lg(r - l);
return max(mx[lg][l], mx[lg][r - (1<<lg)]);
}
// make it 1 based
struct bit {
vector<int> val;
int n;
bit(int _n) : n(_n) {
val.resize(n + 1);
}
void add(int i, int v) {
for (++i;i <= n;i += i&-i)
val[i] += v;
}
int qry(int k) {
int res = 0;
for (int i = 1<<LG;i;i>>=1)
if ((res | i) <= n && val[res | i] < k)
k -= val[res |= i];
return res;
}
};
int nxt[MAX_N], dp[MAX_N];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
{
set<int> alive;
bit tree(N);
for (int i = 0;i < N;++i) tree.add(i, 1), alive.insert(i);
for (int i = 0;i < C;++i) {
nxt[i] = i;
int &l = S[i], &r = E[i];
l = tree.qry(l), r = tree.qry(r);
for (auto it = alive.lower_bound(l);it != end(alive);) {
if (*it > r) break;
tree.add(*it, -1);
it = alive.erase(it);
}
}
for (int i = 0;i < N;++i) mx[0][i] = K[i];
for (int d = 1;1 << d <= N;++d)
for (int i = 0;i < N;++i)
mx[d][i] = max(mx[d-1][i], mx[d-1][ min(N - 1, i + (1<<(d-1))) ]);
}
for (int i = C-1;i >= 0;--i) {
int enemy = qry(S[i], E[i]);
if (enemy > R) continue;
dp[i] = 1;
for (int j = i + 1;j < C;++j) {
if (S[j] <= S[i] && E[j] >= E[i]) {
dp[i] += dp[j];
break;
}
}
}
int win = 0, pos = 0;
for (int i = 0;i < N;++i) {
for (int j = 0;j < C;++j) {
if (S[j] <= i && E[j] >= i) {
if (chmax(win, dp[j]))
pos = i;
break;
}
}
}
DE(win, pos);
return pos;
}
