#include <vector>
#include <list>
#include <iterator>
#include <set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T, class C = less<>>
using ordered_set = tree<T, null_type, C, rb_tree_tag, tree_order_statistics_node_update>;
struct cell
{
int i, l, r;
cell(int i, int l, int r) : i(i), l(l), r(r)
{}
};
struct cmp
{
bool operator()(list<cell>::iterator a, list<cell>::iterator b)
{
return a->i < b->i;
}
};
void convert(int n, vector<pair<int, int>> &rounds)
{
list<cell> cells;
for (int i = 0; i < n; ++i) cells.emplace_back(i, i, i);
ordered_set<list<cell>::iterator, cmp> help;
for (auto it = cells.begin(); it != cells.end(); ++it) help.insert(it);
for (auto &[l, r] : rounds)
{
auto itL = *help.find_by_order(l), itR = *help.find_by_order(r);
r = itL->r = itR->r;
l = itL->l;
for (auto i = itR; i != itL; --i)
{
help.erase(i);
i = cells.erase(i);
}
}
}
int GetBestPosition(int n, int c, int r, int *K, int *S, int *E)
{
vector<int> ranks(n - 1);
for (int i = 0; i < n - 1; ++i) ranks[i] = K[i];
vector<pair<int, int>> rounds(c);
for (int i = 0; i < c; ++i) rounds[i] = {S[i], E[i]};
convert(n, rounds);
vector<pair<vector<int>, vector<int>>> se(n);
for (int i = 0; i < rounds.size(); ++i)
{
se[rounds[i].first].first.push_back(i);
se[rounds[i].second].second.push_back(i);
}
set<int> lose;
ordered_set<int> win;
pair<int, int> res{0, 0};
for (int p = 0; p < n; ++p)
{
for (int i : se[p].first)
{
bool isWin = true;
for (int j = rounds[i].first; j < rounds[i].second; ++j) isWin = isWin && (ranks[j] < r);
if (isWin) win.insert(i);
else lose.insert(i);
}
int last = n + 1;
if (!lose.empty()) last = *lose.begin();
res = max(res, {win.order_of_key(last), -p});
for (int i : se[p].second)
{
lose.erase(i);
win.erase(i);
}
}
return -res.second;
}
