#include <bits/stdc++.h>
using namespace std;
struct BIT{
vector<int> bit;
int n;
BIT(int size){
n = size + 5;
bit.assign(n,0);
}
void upd(int pos,int val){
for(++pos;pos < n;pos += pos & -pos){
bit[pos] += val;
}
}
int get(int pos){
int ret = 0;
for(++pos;pos > 0;pos -= pos & -pos){
ret += bit[pos];
}
return ret;
}
int get_kth(int k){
int pos = 0;
for(int i = 20;i>=0;i--){
if( (pos + (1<<i)) < n && bit[pos + (1<<i)] < k){
k -= bit[pos + (1<<i)];
pos += (1<<i);
}
}
return pos;
}
};
struct SegTree{
vector<pair<int,int>> t;
int n;
SegTree(int size){
n = size + 5;
t.assign(4*n,{2e9,-2e9});
}
void upd(int v,int tl,int tr,int pos,pair<int,int> val){
if(tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm){
upd(v*2,tl,tm,pos,val);
}
else upd(v*2+1,tm+1,tr,pos,val);
t[v].first = min(t[v*2].first,t[v*2+1].first);
t[v].second = max(t[v*2].second,t[v*2+1].second);
}
int get(int v,int tl,int tr,pair<int,int> val){
if(t[v].first > val.first && t[v].second < val.second){
return -1;
}
if(tl == tr)
return tl;
int tm = (tl + tr)/2;
int tmp = get(v*2,tl,tm,val);
if(tmp != -1)
return tmp;
return get(v*2+1,tm+1,tr,val);
}
void upd(int pos,pair<int,int> val){
upd(1,0,n-1,pos,val);
}
int get(pair<int,int> val){
return get(1,0,n-1,val);
}
};
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
BIT btl(n),btr(n);
for(int i = 0;i<n;i++){
btl.upd(i,1);
btr.upd(i,1);
}
vector<pair<int,int>> ranges;
for(int i = 0;i<c;i++){
ranges.push_back({btl.get_kth(s[i] + 1),btr.get_kth(e[i] + 1)});
for(int j = 0;j<e[i]-s[i];j++){
btl.upd(btl.get_kth(s[i] + 2),-1);
btr.upd(btr.get_kth(s[i] + 1),-1);
}
}
int ans1 = -1,ans2 = -1;
vector<pair<int,int>> st[n + 5],nd[n + 5];
for(int i = 0;i<c;i++){
st[ranges[i].first].push_back({ranges[i].second,i});
nd[ranges[i].second + 1].push_back({ranges[i].first,i});
}
SegTree t(c);
BIT bt(c);
int pl = -1,pr = -1;
for(int i = 0;i<n;i++){
if(i && k[i] > r)
pl = i;
while(pr != n && (pr < i || k[pr] < r)){
pr++;
}
for(auto u:st[i]){
t.upd(u.second,{i,u.first});
bt.upd(u.second,1);
}
for(auto u:nd[i]){
t.upd(u.second,{2e9,-2e9});
bt.upd(u.second,-1);
}
int num = t.get({pl,pr+1});
if(num == -1)num = c;
//cout << pl << " " << pr << endl;
if(bt.get(num-1) > ans1){
ans1 = bt.get(num-1);
ans2 = i;
}
}
return ans2;
}
