#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int off = (1<<17);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
int t[off<<1];
bool rem[off << 1];
int unit = 0;
void pull(int idx){
t[idx] = t[ls] + t[rs];
}
void update(int idx, int u){
t[idx+=off] = u;
while (idx/=2)
pull(idx);
}
void push(int idx){
if (!rem[idx]) return;
t[idx] = 0;
if (idx < off){
rem[ls] = 1;
rem[rs] = 1;
}
rem[idx] = 0;
}
void remRange(int l, int r, int idx=1, int lo=0, int hi=off){
push(idx);
if (r <= lo || hi <= l)
return;
if (l <= lo && hi <= r){
rem[idx] = 1;
push(idx);
return ;
}
int mi = (lo+hi)>>1;
remRange(l, r, ls, lo, mi);
remRange(l, r, rs, mi, hi);
pull(idx);
}
int get(int l, int r, int idx=1, int lo=0, int hi=off){
push(idx);
if (r <= lo || hi <= l)
return unit;
if (l <= lo && hi <= r)
return t[idx];
int mi = (lo+hi)>>1;
return get(l, r, ls, lo, mi) + get(l, r, rs, mi, hi);
}
int find(int idx, int pos){
push(idx);
if (idx >= off) return idx - off;
push(ls);
if (t[ls] >= pos){
return find(ls, pos);
}
return find(rs, pos - t[ls]);
}
} seg;
struct range {
int l, r;
range(int L = off - 1, int R = off - 1) : l(L), r(R) {}
friend bool operator <(range lhs, range rhs){
if (lhs.l != rhs.l) return lhs.l > rhs.l;
return lhs.r < rhs.r;
}// last cover most
bool operator ==(range rhs){
return l == rhs.l && r == rhs.r;
}
bool operator !=(range rhs){
return l != rhs.l || r != rhs.r;
}
};
struct sgt3 {
#define ls (idx<<1)
#define rs (idx<<1|1)
int t[off<<1];
int unit = 0;
void pull(int idx){
t[idx] = max(t[ls], t[rs]);
}
void update(int idx, int u){
t[idx+=off] = u;
while (idx/=2)
pull(idx);
}
int get(int l, int r, int idx=1, int lo=0, int hi=off){
if (r <= lo || hi <= l)
return unit;
if (l <= lo && hi <= r)
return t[idx];
int mi = (lo+hi)>>1;
return max(get(l, r, ls, lo, mi), get(l, r, rs, mi, hi));
}
} seg3;
struct sgt2 {
#define ls (idx<<1)
#define rs (idx<<1|1)
range t[off << 1];
int cnt[off << 1];
range unit = range(off - 1, off - 1);
void pull(int idx){
t[idx] = max(t[ls], t[rs]);
cnt[idx] = cnt[ls] + cnt[rs];
}
void update(int idx, range u, int c = 1){
t[idx+=off] = u;
cnt[idx] = c;
while (idx/=2)
pull(idx);
}
range get(int l, int r, int idx=1, int lo=0, int hi=off){
if (r <= lo || hi <= l)
return unit;
if (l <= lo && hi <= r)
return t[idx];
int mi = (lo+hi)>>1;
return max(get(l, r, ls, lo, mi), get(l, r, rs, mi, hi));
}
int getIdx(int l, int r, int idx=1, int lo=0, int hi=off){
if (r <= lo || hi <= l)
return 0;
if (l <= lo && hi <= r)
return cnt[idx];
int mi = (lo+hi)>>1;
return getIdx(l, r, ls, lo, mi) + getIdx(l, r, rs, mi, hi);
}
} seg2;
vector<int> add[MAXN], rem[MAXN];
int GetBestPosition(int n, int m, int R, int K[], int S[], int E[]){
for (int i = 1; i <= n + 1; i++){
seg.update(i, 1);
}
vector<range> ranges(m);
for (int i = 0; i < m; i++){
ranges[i] = range(seg.find(1, S[i] + 1), seg.find(1, E[i] + 2) - 1);
seg.remRange(ranges[i].l + 1, ranges[i].r + 1);
}
sort(all(ranges));
for (int i = 0; i < m; i++){
add[ranges[i].l].pb(i);
rem[ranges[i].r].pb(i);
//cout << ranges[i].l << ' ' << ranges[i].r << endl;
}
vector<int> a(n + 1);
a[1] = R;
for (int i = 2; i <= n; i++){
a[i] = K[i - 2];
}
for (int i = 1; i <= n; i++){
seg3.update(i, a[i]);
}
pii ans = {-inf, -inf};
//cout << endl;
for (int i = 1; i <= n; i++){
if (i != 1){
swap(a[i], a[i - 1]);
seg3.update(i, a[i]);
seg3.update(i - 1, a[i - 1]);
}
for (auto u : add[i]){
seg2.update(u, ranges[u], 1);
}
int lo = -1, hi = off - 1;
while (hi - lo > 1){
int mi = (lo + hi) / 2;
range tm = seg2.get(0, mi + 1);
if (seg3.get(tm.l, tm.r + 1) <= R){
lo = mi;
} else {
hi = mi;
}
}
ckmax(ans, {seg2.getIdx(0, hi), -(i - 1)});
for (auto u : rem[i]){
seg2.update(u, seg2.unit, 0);
}
}
return -ans.S;
}
