#include <bits/stdc++.h>
using namespace std;
struct minSegtree{
int n;
vector<int> arr;
vector<int> tree;
minSegtree(vector<int> temp){
int n = temp.size();
arr = temp;
tree.assign(4*n, 0);
build(0, 0, n-1);
}
void build(int ncur, int nleft, int nright){
if(nleft==nright){
tree[ncur] = arr[nleft];
}
else{
int nmid = (nleft+nright)/2;
build(2*ncur+1, nleft, nmid);
build(2*ncur+2, nmid+1, nright);
tree[ncur] = min(tree[2*ncur+1], tree[2*ncur+2]);
}
}
int query(int qleft, int qright, int ncur, int nleft, int nright){
if(qleft>nright || qright<nleft){
return n+1;
}
else if(qleft<=nleft && nright<=qright){
return tree[ncur];
}
else{
int nmid = (nleft+nright)/2;
return min(query(qleft, qright, 2*ncur+1, nleft, nmid), query(qleft, qright, 2*ncur+2, nmid+1, nright));
}
}
};
struct rangeSegtree{
int n;
vector<int> arr;
vector<int> tree;
rangeSegtree(int _n): n(_n){
arr.assign(n+1, 0);
tree.assign(4*n+4, 0);
}
int privgetsum(int qleft, int qright, int ncur, int nleft, int nright){
if(qleft>nright || qright<nleft){
return 0;
}
else if(qleft<=nleft && nright<=qright){
return tree[ncur];
}
else{
int nmid = (nleft+nright)/2;
return privgetsum(qleft, qright, 2*ncur+1, nleft, nmid) + privgetsum(qleft, qright, 2*ncur+2, nmid+1, nright);
}
}
void privupdate(int pos, int val, int ncur, int nleft, int nright){
if(nleft==nright){
arr[pos]+=val;
tree[ncur]+=val;
}
else{
int nmid = (nleft+nright)/2;
if(pos<=nmid){
privupdate(pos, val, 2*ncur+1, nleft, nmid);
}
else{
privupdate(pos, val, 2*ncur+2, nmid+1, nright);
}
tree[ncur]=tree[2*ncur+1]+tree[2*ncur+2];
}
}
void update(int left, int right){
privupdate(left, 1, 0, 0, n);
privupdate(right+1, -1, 0, 0, n);
}
int getAns(){
int maxx = 0;
int ans = 0;
for(int i=0; i<n; i++){
int temp = privgetsum(0, i, 0, 0, n);
if(temp>maxx){
maxx = temp;
ans = i;
}
}
return ans;
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
vector<int> arr;
for(int i=0; i<N-1; i++){
arr.push_back(K[i]);
}
minSegtree tree(arr);
rangeSegtree range(N);
for(int i=0; i<C; i++){
if(tree.query(S[i], E[i]-1, 0, 0, N)<R){
range.update(S[i], E[i]);
}
}
return range.getAns();
}
