#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<int>
#define ll long long int
using namespace std;
const int mxn = 1e5 + 5;
int tree[mxn * 4];
int n;
void update(int k, int x){
k += n;
tree[k] = x;
for(k/=2;k>=1;k/=2){
tree[k] = max(tree[k*2], tree[k*2 + 1]);
}
}
int quer(int l, int r){
l += n;
r += n;
int ret = 0;
while(l <= r){
if(l % 2 == 1){
ret = max(ret, tree[l++]);
}
if(r % 2 == 0){
ret = max(ret, tree[r--]);
}
l/=2; r/=2;
}
return ret;
}
vi rupq(mxn * 4, 0);
void add(int k, int x){
k += n + 1;
rupq[k] += x;
for(k/=2;k>=1;k/=2){
rupq[k] = rupq[k * 2] + rupq[k * 2 + 1];
}
}
int quer2(int l, int r){
l += n + 1;
r += n + 1;
int ret = 0;
while(l <= r){
if(l % 2 == 1)ret += rupq[l++];
if(r % 2 == 0)ret += rupq[r--];
l/=2;
r/=2;
}
return ret;
}
void rangeadd(int l, int r, int x){
add(l, x);
if(r != n){
add(r + 1, -x);
}
}
int GetBestPosition(int N, int C, int R, int *w, int *S, int *E) {
n = N-1;
vector<pair<int,int>>quers(C);
vector<int> v(N+1);
for(int i=0; i<=N; i++){
v[i] = i;
}
for(int i=0; i<C; i++){
int rs = v[S[i]];
int re = v[E[i]+1]-1;
/*cerr << rs << ' ' << re << '\n';
for(auto j: v){
cerr << j << ' ';
}
cerr << '\n';*/
quers[i] = {rs,re};
/*for(int j=S[i]+1; j<=E[i]; j++){
v.erase(v.begin()+S[i]+1);
}*/
v.erase(v.begin()+S[i]+1, v.begin()+E[i]+1);
}
f0r(i, N-1){
update(i, w[i]);
}
//if(N <= 5000){
f0r(i, C){
int l = quers[i].first;
int r = quers[i].second - 1;
if(quer(l, r) < R){
//cout<<l<<' '<<r+1<<'\n';
//cout<<quer(l,r)<<'\n';
rangeadd(l, r+1, 1);
}
}
int mx = 0;
int ans = 0;
vi diffarr;
f0r(i,N){
diffarr.pb(rupq[i + N]);
}
vi realarr;
realarr.pb(diffarr[0]);
for(int i=1;i<N;i++){
realarr.pb(realarr[i-1] + diffarr[i]);
}
f0r(i, N){
//cout<<quer2(0,i)<<' ';
if(realarr[i] > mx){
mx = realarr[i];
ans = i;
}
}
//cout<<'\n';
return ans;
//}
//else return 0;
}
