#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
tree_order_statistics_node_update>
tin;
const int maxn = 200000;
int seg[4 * maxn];
int *arr;
void build(int curin, int curl, int curr) {
if (curl == curr) {
seg[curin] = arr[curl];
return;
}
build(curin * 2 + 1, curl, (curl + curr) / 2),
build(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
seg[curin] = max(seg[curin * 2 + 1], seg[curin * 2 + 2]);
}
int query(int curin, int curl, int curr, int ql, int qr) {
if (curl > qr || curr < ql) return INT_MIN;
if (ql <= curl && curr <= qr) return seg[curin];
return max(query(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
query(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr));
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for (int i = 0; i < N; i++) tin.insert(make_pair(i, i));
vector<pair<int, int>> vpii;
for (int i = 0; i < C; i++) {
pair<int, int> newone;
newone.first = tin.find_by_order(S[i])->first;
newone.second = tin.find_by_order(E[i])->second;
for (int j = E[i]; j >= S[i]; j--) tin.erase(tin.find_by_order(j));
tin.insert(newone);
vpii.push_back(newone);
}
arr = K;
build(0, 0, N - 2);
int things[maxn + 1];
for (auto [a, b] : vpii) {
int maxi = query(0, 0, N - 2, a, b - 1);
// cout << a << " " << b << " " << maxi << "\n";
if (maxi < R) {
things[a]++;
things[b + 1]--;
}
}
int cur = 0;
int maxi = -1, maxid = -1;
for (int i = 0; i < N; i++) {
cur += things[i];
if (cur > maxi) {
maxi = cur;
maxid = i;
}
}
return maxid;
}
