#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN = 1e5+5, inf = 1e9;
int n;
namespace seg1 {
int seg[MXN<<2];
bool lz[MXN<<2];
void build(int l=0, int r=n, int id=1) {
seg[id] = r-l;
lz[id] = 0;
if(r-l == 1) return;
build(l, mid, lc);
build(mid, r, rc);
}
inline void apply(int id) {
seg[id] = 0;
lz[id] = 1;
}
inline void push(int l, int r, int id) {
if(r-l>1 && lz[id]) {
apply(lc);
apply(rc);
}
lz[id] = 0;
}
void upd(int s, int e, int l=0, int r=n, int id=1) {
if(s>=r || l>=e) return;
if(s<=l && r<=e) return apply(id);
push(l, r, id);
upd(s, e, l, mid, lc);
upd(s, e, mid, r, rc);
seg[id] = seg[lc] + seg[rc];
}
int find(int x, int l=0, int r=n, int id=1) {
if(seg[id]<x) return -1;
if(r-l == 1) return l;
push(l, r, id);
int res = find(x, l, mid, lc);
return res==-1 ? find(x-seg[lc], mid, r, rc) : res;
}
}
namespace seg2 {
pll seg[MXN<<2];
ll lz[MXN<<2];
void build(int l=0, int r=n, int id=1) {
seg[id] = pll(0, -l);
if(r-l == 1) return;
build(l, mid, lc);
build(mid, r, rc);
}
void upd(int s, int e, int x, int l=0, int r=n, int id=1) {
if(s>=r || l>=e) return;
if(s<=l && r<=e) {
seg[id].first += x;
lz[id] += x;
return;
}
upd(s, e, x, l, mid, lc);
upd(s, e, x, mid, r, rc);
seg[id] = max(seg[lc], seg[rc]);
seg[id].first += lz[id];
}
}
int GetBestPosition(int n, int C, int R, int *a, int *s, int *e) {
::n = n;
seg1::build();
for(int i=0; i<C; i++) {
s[i] = seg1::find(s[i]+1);
e[i] = seg1::find(e[i]+2);
if(e[i]==-1) e[i] = n;
e[i]--;
seg1::upd(s[i]+1, e[i]+1);
}
vector<pii> segs;
int lst=-1;
for(int i=0; i<n-1; i++)
if(a[i]>R) {
if(i-lst>1)
segs.push_back({lst+1, i});
lst = i;
}
if(n-1-lst>1)
segs.push_back({lst+1, n-1});
pll ans = {-1, -1};
seg2::build();
for(int i=0; i<C; i++) {
int pos = lower_bound(segs.begin(), segs.end(), pii(s[i]+1, 0))-segs.begin()-1;
if(pos>=0 && segs[pos].second>=e[i])
seg2::upd(s[i], e[i]+1, 1);
else
seg2::upd(s[i], e[i], -inf);
ans = max(ans, seg2::seg[1]);
}
return -ans.second;
}
