#include <bits/stdc++.h>
using namespace std;
int n, c, r;
vector<int> s, e, p;
vector< vector<int> > adj;
vector<int> pai;
vector<int> id;
vector<int> label;
int sz;
int add_node(vector<int> &children) {
adj.push_back({});
pai.push_back(-1);
id.push_back(sz);
for (int x: children) {
id[sz] = min(id[sz], id[x]);
pai[x] = sz;
adj[sz].push_back(x);
}
int ret = sz;
sz++;
return ret;
}
void print_node(int idx) {
cerr << idx << ": ";
cerr << "pai = " << pai[idx] << " | filhos =";
for (int x: adj[idx]) {
cerr << " " << x;
}
cerr << "\n";
}
void build_tree() {
vector<int> players;
for (int i = 0; i < n; i++) {
add_node(players);
}
vector<int> rep(c);
for (int i = 0; i < c; i++) {
vector<pair<int,int>> heads;
for (int j = 0; j < sz; j++) {
if (pai[j] == -1) {
heads.push_back({id[j], j});
}
}
sort(heads.begin(), heads.end());
players.clear();
for (int j = s[i]; j <= e[i]; j++) {
players.push_back(heads[j].second);
}
rep[i] = add_node(players);
}
cerr << "Finished building tree:\n";
cerr << "Leaves:\n";
for (int i = 0; i < n; i++) {
print_node(i);
}
cerr << "Non-leaves:\n";
for (int i = n; i < sz; i++) {
print_node(i);
}
}
int cnt_cur;
void dfs(int v) {
if (adj[v].empty()) {
return;
} else {
label[v] = label[adj[v][0]];
for (int x: adj[v]) {
dfs(x);
label[v] = max(label[v], label[x]);
}
if (label[v] == r) {
cnt_cur++;
}
}
}
int get_wins(vector<int> &v, int pos) {
label.resize(sz);
for (int i = 0; i < n; i++) {
label[i] = v[i];
}
cnt_cur = 0;
dfs(sz - 1);
return cnt_cur;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N; c = C; r = R; s.clear(); e.clear(); p.clear();
for (int i = 0; i < n; i++) {
p.push_back(K[i]);
}
for (int i = 0; i < c; i++) {
s.push_back(S[i]);
e.push_back(E[i]);
}
build_tree();
int best_resp = -1, best_pos = -1;
for (int pos = 0; pos < n; pos++) {
vector<int> vals;
for (int i = 0; i < pos; i++) {
vals.push_back(p[i]);
}
vals.push_back(r);
for (int i = pos; i < n - 1; i++) {
vals.push_back(p[i]);
}
int cur = get_wins(vals, pos);
if (cur > best_resp) {
best_resp = cur;
best_pos = pos;
}
}
return best_pos;
}
