#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, maxN = 4e5 + 5, lgn = 18;
int n, q, a[maxn];
int seg[maxN][2];
void build(int id, int l, int r, int i) {
if (l==r) {
seg[id][i] = 1;
return;
}
int mid = (l+r)/2;
build(id*2, l, mid, i); build(id*2+1, mid+1, r, i);
seg[id][i] = seg[id*2][i] + seg[id*2+1][i];
}
void update(int id, int l, int r, int findl, int findr, int i) {
if (findr<l || r<findl) return;
if (findl<=l && r<=findr && seg[id][i]==0) return;
if (l==r) {
seg[id][i] = 0;
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, findl, findr, i); update(id*2+1, mid+1, r, findl, findr, i);
seg[id][i] = seg[id*2][i] + seg[id*2+1][i];
}
int qry(int id, int l, int r, int val, int lhs, int i) {
if (l==r) return l;
int mid = (l+r)/2;
if (seg[id*2][i] + lhs >= val) return qry(id*2, l, mid, val, lhs, i);
return qry(id*2+1, mid+1, r, val, lhs + seg[id*2][i], i);
}
int st[maxn][lgn];
void buildst() {
for (int i=0;i<n;i++) for (int j=0;j<lgn;j++) st[i][j] = -1;
for (int i=n-1;i>=0;i--) {
st[i][0] = a[i];
for (int j=1;j<lgn;j++) {
if (i + (1<<j) - 1 > n-1) break;
st[i][j] = max(st[i][j-1], st[i + (1<<(j-1))][j-1]);
}
}
}
int mx(int l, int r) {
int lg = log2(r-l+1);
return max(st[l][lg], st[r - (1<<lg) + 1][lg]);
}
int fen[maxn];
void update1(int id, int val) {
while (id<maxn) {
fen[id] += val;
id += (id & -id);
}
}
int qry1(int id) {
int val = 0;
while (id >= 1) {
val += fen[id];
id -= (id & -id);
}
return val;
}
int GetBestPosition(int N, int Q, int R, int *K, int *S, int *E) {
n = N, q = Q;
for (int i=0;i<n-1;i++) a[i] = K[i];
build(1, 0, n-1, 0); build(1, 0, n-1, 1);
buildst();
for (int i=0;i<Q;i++) {
int l = qry(1, 0, n-1, S[i]+1, 0, 0);
int r = qry(1, 0, n-1, E[i]+1, 0, 1);
if (mx(l, r-1) < R) {
update1(l+1, 1);
update1(r+2, -1);
}
update(1, 0, n-1, l+1, r, 0);
update(1, 0, n-1, l, r-1, 1);
}
int mx = -1, ans = -1;
for (int i=0;i<n;i++) {
int val = qry1(i+1);
if (val > mx) mx = val, ans = i;
}
return ans;
}
