#include<bits/stdc++.h>
using namespace std;
int seg[400005];
int v[400005];
int tmp[400005];
int l[100005], r[100005];
int seg2[400005];
int k[100005];
void seg_set(int x, int l, int r, int p, int v) {
if(l==r) {
seg[x] = v;
} else {
if(p<=(l+r)/2) seg_set(x*2, l, (l+r)/2, p, v);
else seg_set(x*2+1, (l+r)/2+1, r, p, v);
seg[x] = seg[x*2] + seg[x*2+1];
}
}
int seg_qry(int x, int l, int r, int v) {
if(l==r) return l;
else {
if(v <= seg[x*2]) return seg_qry(x*2, l, (l+r)/2, v);
else return seg_qry(x*2+1, (l+r)/2+1, r, v-seg[x*2]);
}
}
void seg2_build(int x, int l, int r) {
if(l==r) seg2[x] = k[l];
else {
seg2_build(x*2, l, (l+r)/2);
seg2_build(x*2+1, (l+r)/2+1, r);
seg2[x] = max(seg2[x*2], seg2[x*2+1]);
}
}
int seg2_qry(int x, int l, int r, int ll, int rr) {
if(l > rr || r < ll) return -1e9;
if(ll <= l && r <= rr) return seg2[x];
return max(seg2_qry(x*2, l, (l+r)/2, ll, rr), seg2_qry(x*2+1, (l+r)/2+1, r, ll, rr));
}
int diff[100005];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for(int i=0; i<N; i++) seg_set(1, 0, N-1, i, 1);
for(int i=0; i<C; i++) {
S[i]++; E[i]++;
for(int j=S[i]; j<=E[i]; j++) {
tmp[j] = seg_qry(1, 0, N-1, j);
}
l[i] = tmp[S[i]];
r[i] = tmp[E[i]] + v[tmp[E[i]]];
for(int j=S[i]+1; j<=E[i]; j++) {
v[tmp[S[i]]] += v[tmp[j]];
seg_set(1, 0, N-1, tmp[j], 0);
}
v[tmp[S[i]]] += (E[i] - S[i]);
}
for(int i=0; i<N-1; i++) k[i] = K[i];
seg2_build(1, 0, N-2);
for(int i=0; i<C; i++) {
if(R > seg2_qry(1, 0, N-2, l[i], r[i]-1)) {
diff[l[i]]++;
diff[r[i]+1]--;
}
}
int ans = -1, pos = -1;
for(int i=0; i<N; i++) {
if(i) diff[i] += diff[i-1];
if(diff[i] > ans) {
ans = diff[i];
pos = i;
}
}
return pos;
}
