#include "tournament.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// int main() {
// int tmp;
// int N, C, R;
// int *K, *S, *E;
// tmp = scanf("%d %d %d", &N, &C, &R);
// assert(tmp == 3);
// K = (int *) malloc((N - 1) * sizeof(int));
// S = (int *) malloc(C * sizeof(int));
// E = (int *) malloc(C * sizeof(int));
// for (int i = 0; i < N - 1; i++) {
// tmp = scanf("%d", &K[i]);
// assert(tmp == 1);
// }
// for (int i = 0; i < C; i++) {
// tmp = scanf("%d %d", &S[i], &E[i]);
// assert(tmp == 2);
// }
// printf("%d\n", GetBestPosition(N, C, R, K, S, E));
// }
int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]) {
ordered_set o;
for (int i = 0; i <= N; i++) o.insert(i);
vector<pair<int, int>> og;
for (int i = 0; i < C; i++) {
int s = *o.find_by_order(S[i]);
int e = *o.find_by_order(E[i]+1)-1;
og.push_back({s, e});
for (int j = S[i]+1; j <= E[i]; j++) o.erase(o.find_by_order(S[i]+1));
}
vector<int> wins(N);
for (int i = 0; i < og.size(); i++) {
auto [s, e] = og[i];
bool poss = true;
for (int j = s; j < e; j++) {
if (K[j] > R) {
poss = false;
break;
}
}
if (!poss) continue;
// each position is only considered for every time it is in a tournament, so it's not actually N^2
for (int j = s; j < e; j++) wins[j]++;
}
return max_element(wins.begin(), wins.end())-wins.begin();
}
