#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, q, s;
int a[MAXN], Le[MAXN], Ri[MAXN];
int far[MAXN], Left[MAXN], Right[MAXN];
int st[4 * MAXN];
void build(int id, int l, int r){
if(l == r){
st[id] = 1;
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void update(int pos, int val){
int id = 1, l = 1, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(pos <= mid) id = id << 1, r = mid;
else id = id << 1 | 1, l = mid + 1;
}
st[id] = val;
while(id > 1){
id >>= 1;
st[id] = st[id << 1] + st[id << 1 | 1];
}
}
int walk(int val){
int id = 1, l = 1, r = n;
while(1){
if(l == r) return l;
int mid = (l + r) >> 1;
if(st[id << 1] < val){
val-= st[id << 1];
l = mid + 1;
id = id << 1 | 1;
} else{
r = mid;
id = id << 1;
}
}
return l;
}
int rmq[MAXN][20];
void work(){
for(int i = 1; i <= n - 1; i++) rmq[i][0] = a[i];
for(int j = 1; (1 << j) <= n; j++){
for(int i = 1; i + (1 << (j)) - 1 <= n; i++){
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
}
int get(int l, int r){
int k = __lg(r - l + 1);
return max(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int f[MAXN];
int GetBestPosition(int n, int q, int k, int *K, int *L, int *R){
s = k;
for(int i = 1; i < n; i++) a[i] = K[i - 1];
for(int i = 1; i <= q; i++){
Le[i] = L[i - 1];
Ri[i] = R[i - 1];
Le[i]++; Ri[i]++;
}
for(int i = 1; i <= n; i++) far[i] = i;
build(1, 1, n);
work();
for(int i = 1; i <= q; i++){
int l = Le[i], r = Ri[i];
int p = walk(l);
for(int j = 1; j <= r - l; j++){
int nxt = walk(Le[i] + 1);
far[p] = far[nxt];
update(nxt, 0);
}
Left[i] = p;
Right[i] = far[p];
}
for(int i = 1; i <= q; i++){
if(s > get(Left[i], Right[i] - 1)){
f[Left[i]]++;
f[Right[i]]--;
}
}
for(int i = 1; i <= n; i++) f[i] = f[i - 1] + f[i];
return max_element(f + 1, f + 1 + n) - f - 1;
}
//int main(){
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #define taskname "kieuoanh"
// if(fopen(taskname".inp", "r")){
// freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
// }
// cin >> n >> q >> s;
// for(int i = 1; i <= n - 1; i++){
// cin >> a[i];
// }
// for(int i = 1; i <= q; i++){
// cin >> L[i] >> R[i];
// L[i]++; R[i]++;
// }
// for(int i = 1; i <= n; i++) far[i] = i;
// build(1, 1, n);
// work();
//
// for(int i = 1; i <= q; i++){
// int l = L[i], r = R[i];
// int p = walk(l);
// for(int j = 1; j <= r - l; j++){
// int nxt = walk(L[i] + 1);
// far[p] = far[nxt];
// update(nxt, 0);
// }
// Left[i] = p;
// Right[i] = far[p];
// }
//
// for(int i = 1; i <= q; i++){
// if(s > get(Left[i], Right[i] - 1)){
// f[Left[i]]++;
// f[Right[i]]--;
// }
// }
// for(int i = 1; i <= n; i++) f[i] = f[i - 1] + f[i];
//
// cout << max_element(f + 1, f + 1 + n) - f - 1;
//
// return 0;
//}
