#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
const int LOG = 20;
int f[LOG+1][2*MAXN];
pair<int, int> rngs[2*MAXN];
int hsb(int x) {
return 31 - __builtin_clz(x);
}
struct Node {
int actives, rngId;
Node (int _actives=0, int _rngId=-1): actives(_actives), rngId(_rngId) {}
Node operator+(Node right) {
Node left = *this;
return Node(left.actives + right.actives);
}
};
struct SEG {
vector<Node> seg; int n;
SEG (int _n=0) {
n = 1;
while (n < _n) n <<= 1;
seg = vector<Node> (2*n);
for (int i=0; i<_n; i++) {
seg[i+n] = Node(1, i);
}
for (int v=n-1; v>0; v--)
seg[v] = seg[getLeft(v)] + seg[getRight(v)];
}
int getLeft(int v) {
return 2*v;
}
int getRight(int v) {
return 2*v+1;
}
void put(int v, int l, int r, int i, Node val) {
if (l == r) {
seg[v] = val;
return;
}
int m = (l + r) / 2;
if (i <= m) put(getLeft(v), l, m, i, val);
else put(getRight(v), m+1, r, i, val);
seg[v] = seg[getLeft(v)] + seg[getRight(v)];
}
pair<int, int> xTh(int v, int l, int r, int x) {
if (l == r) {
return {l, seg[v].rngId};
}
int m = (l + r) / 2;
if (seg[getLeft(v)].actives >= x)
return xTh(getLeft(v), l, m, x);
else return xTh(getRight(v), m+1, r, x - seg[getLeft(v)].actives);
}
};
struct SparseTable {
vector<int> fl[LOG+1], fr[LOG+1];
SparseTable(vector<int> a) {
int n = (int)a.size();
for (int b=0; b<=LOG; b++) {
fl[b] = vector<int> (n, 0);
fr[b] = vector<int> (n, 0);
}
for (int i=0; i<n; i++) fl[0][i] = fr[0][i] = a[i];
for (int b=1; b<=LOG; b++) {
for (int i=0; i<n; i++) {
if (i+1 >= (1 << b))
fl[b][i] = max(fl[b-1][i], fl[b-1][i-(1 << (b-1))]);
if (n-i >= (1 << b))
fr[b][i] = max(fr[b-1][i], fr[b-1][i+(1 << (b-1))]);
}
}
}
int mx(int l, int r) {
int sz = (r - l + 1);
return max(fl[hsb(sz)][r], fr[hsb(sz)][l]);
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int n = N;
vector<int> ranks;
for (int i=0; i<n-1; i++) ranks.push_back(K[i]);
SparseTable table(ranks);
for (int i=0; i<n; i++) {
rngs[i] = {i, i};
f[0][i] = -1;
}
SEG seg(n);
for (int round=0, nxtRng=n; round<C; round++, nxtRng++) {
int l = S[round], r = E[round];
f[0][nxtRng] = -1;
for (int i=l; i<=r; i++) {
auto [rngPos, rngId] = seg.xTh(1, 0, seg.n-1, l+1);
seg.put(1, 0, seg.n-1, rngPos, Node());
f[0][rngId] = nxtRng;
if (i == l) rngs[nxtRng].first = rngs[rngId].first;
if (i == r) rngs[nxtRng].second = rngs[rngId].second;
if (i == r) seg.put(1, 0, seg.n-1, rngPos, Node(1, nxtRng));
}
}
// for (int i=0; i<n+C; i++) {
// cout << rngs[i].first << ' ' << rngs[i].second << ' ' << f[0][i] << '\n';
// }
for (int b=1; b<=LOG; b++) {
for (int i=0; i<n+C; i++) {
if (f[b-1][i] == -1) {
f[b][i] = -1;
continue;
}
f[b][i] = f[b-1][f[b-1][i]];
}
}
int bestPos = 0, mxWins = -1;
for (int pos = 0; pos < n; pos++) {
// cout << pos << ':' << '\n';
int wins = 0;
int rng = pos;
for (int b=LOG; b>=0; b--) {
int newRng = f[b][rng];
if (newRng == -1) continue;
auto [l, r] = rngs[newRng];
// cout << "test" << newRng << ' ' << l << ' ' << r << '=' << table.mx(l, r-1) << '\n';
if (l < r and table.mx(l, r-1) > R) continue;
rng = newRng;
wins += (1 << b);
}
// cout << wins << '\n' << '\n';
if (wins > mxWins) {
mxWins = wins;
bestPos = pos;
}
}
return bestPos;
}
// int main() {
// int n; cin >> n;
// vector<int> a(n);
// for (int i=0; i<n; i++) cin >> a[i];
// SparseTable table(a);
// while (true) {
// int l, r; cin >> l >> r;
// cout << table.mx(l, r) << '\n';
// }
// return 0;
// }
