//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#define ll long long
#define maxn 200005
#define mod 1000000000
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
vector<int> node[maxn];
int block[maxn];
pii getpos(int x) {
int cnt = 0;
while (true) {
if (x < block[cnt]) {
return make_pair(cnt, x);
}
x -= block[cnt];
cnt++;
}
}
int a[maxn], dep[maxn];
int tot;
vector<int> adj[maxn];
int best[maxn];
pii range[maxn];
void dfs(int n, int par) {
if (n < tot) {
range[n] = make_pair(n, n);
best[n] = n;
} else {
range[n] = make_pair(1<<30, -1);
}
for (int v:adj[n]) {
if (v != par) {
dfs(v, n);
if (dep[v] + 1 > dep[n]) {
dep[n] = dep[v] + 1;
best[n] = best[v];
}
range[n] = make_pair(min(range[n].ff, range[v].ff), max(range[n].ss, range[v].ss));
}
}
}
int sp[17][maxn];
inline int hbit(int x) {
int ret = 0;
while (x) {
ret++, x>>=1;
}
return ret;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
tot = N;
for (int i = 0;i < N - 1;i++) a[i] = K[i];
int blocksiz = int(sqrt(N)), num = (N - 1 + blocksiz) / blocksiz;
int ind = -1;
for (int i = 0;i < N;i++) {
if (i % blocksiz == 0) {
block[ind] = node[ind].size();
ind++;
}
node[ind].push_back(i);
}
block[ind] = node[ind].size();
for (int i = 0;i < C;i++) {
int add = N + i;
pii s = getpos(S[i]), e = getpos(E[i]);
//cout << s.ff << " " << s.ss << endl;
if (s.ff != e.ff) {
for (int j = s.ss;j < node[s.ff].size();j++) {
adj[add].push_back(node[s.ff][j]);
}
for (int j = 0;j < block[s.ff] - s.ss;j++) node[s.ff].pop_back();
node[s.ff].push_back(add);
block[s.ff] = node[s.ff].size();
for (int j = s.ff + 1;j < e.ff;j++) {
for (int k = 0;k < block[j];k++) {
adj[add].push_back(node[j][k]);
}
node[j].clear();
block[j] = 0;
}
for (int j = 0;j <= e.ss;j++) {
adj[add].push_back(node[e.ff][0]);
node[e.ff].erase(node[e.ff].begin());
}
block[e.ff] = node[e.ff].size();
} else {
for (int j = s.ss;j <= e.ss;j++) {
adj[add].push_back(node[s.ff][s.ss]);
node[s.ff].erase(node[s.ff].begin() + s.ss);
}
node[s.ff].insert(node[s.ff].begin() + s.ss, add);
block[s.ff] = node[s.ff].size();
}
/*
cout << add << ": ";
for (int v:adj[add]) {
cout << v << " ";
}
cout << endl;
for (int i = 0;i < num;i++) {
cout << "block " << i << " " << block[i] << endl;
for (int j = 0;j < node[i].size();j++) cout << node[i][j] << " ";
cout << endl;
}
*/
}
dfs(N + C - 1, -1);
/*
for (int i = N;i < N + C;i++) {
cout << range[i].ff << " " << range[i].ss << endl;
}
*/
for (int i = 0;i < N - 1;i++) sp[0][i] = a[i];
for (int i = 1;i < 17;i++) {
for (int j = 0;j < N - 1;j++) {
sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1<<(i - 1))]);
}
}
int an = 0, ap = 0;
for (int i = N;i < N + C;i++) {
int d = hbit(range[i].ss - range[i].ff) - 1;
int val = max(sp[d][range[i].ff], sp[d][range[i].ss - (1<<d)]);
//cout << range[i].ff << " " << range[i].ss - 1 << " " << val << endl;
if (R > val) {
if (dep[i] > an) {
an = dep[i];
ap = best[i];
}
}
}
return ap;
}
/*
int main() {
io
int n, c, r;
cin >> n >> c >> r;
int a[n - 1], s[c], e[c];
for (int i = 0;i < n - 1;i++) cin >> a[i];
for (int i = 0;i < c;i++) cin >> s[i] >> e[i];
cout << GetBestPosition(n, c, r, a, s, e);
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
10 5 5
7 3 2 4 6 8 0 1 9
0 1
4 7
2 3
1 3
0 2
*/
