#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define pb push_back
#define fst first
#define snd second
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
void prop(int,int,int);
vi tsum, tmax, lazy;
vi arr;
void upds(int n){
tsum[n] = tsum[n<<1] + tsum[n<<1|1];
}
void buildsum(int lb, int rb, int n){
if(lb+1==rb) {
tsum[n] = 1;
return;
}
int mb = (lb+rb)/2;
buildsum(lb,mb,n<<1);
buildsum(mb,rb,n<<1|1);
upds(n);
}
void add(int l, int r, int lb, int rb, int n){
//cerr<<l<<" "<<r<<" "<<lb<<" "<<rb<<" "<<n<<endl;
if(l <= lb and rb <= r) {
lazy[n] = 1;
tsum[n] = 0;
return;
}
if(lazy[n]) prop(lb,rb,n);
int mb = (lb+rb)/2;
if(l < mb) add(l,r,lb,mb,n<<1);
if(r > mb) add(l,r,mb,rb,n<<1|1);
upds(n);
}
void prop(int lb, int rb, int n){
int mb = (lb+rb)/2;
add(lb,rb,lb,mb,n<<1);
add(lb,rb,mb,rb,n<<1|1);
lazy[n] = 0;
}
int getidx(int i, int lb, int rb, int n){
if(lb + 1 == rb) return lb;
if(lazy[n]) prop(lb,rb,n);
if(i == tsum[n]) return rb;
int mb = (lb+rb)/2;
if(i < tsum[n<<1]) return getidx(i, lb, mb, n<<1);
return getidx(i-tsum[n<<1], mb,rb,n<<1|1);
}
vii intervals;
vii idx;
INT GetBestPosition(INT N, INT C, INT R, INT *K, INT *S, INT *E) {
idx.resize(N);
lazy.assign(4*N,0);
tsum.assign(4*N,0);
tmax.assign(4*N,0);
buildsum(0, N, 1);
FOR(i,0,N) arr.pb(K[i]);
FOR(i, 0, N) idx[i] = {i,i};
FOR(i, 0, C){
int l = getidx(S[i], 0,N,1), r = getidx(E[i]+1, 0, N, 1) - 1;
intervals.pb({l,r});
add(l+1,r+1,0,N,1);
//cout<<tsum[1]<<endl;
}
//for(ii p : intervals) cout << p.fst << " " << p.snd << endl;
vi val(C, -1);
FOR(i, 0, C) FOR(j, intervals[i].fst, intervals[i].snd){
val[i] = max(val[i], K[j]);
}
ii best = {-1, -1e9};
//for(int k : val) cout << k << endl;
FOR(i, 0, N) {
int tot = 0;
FOR(c,0,C) if(intervals[c].fst <= i and i <= intervals[c].snd){
tot += val[c] < R;
}
best = max(best, {tot,-i});
}
return -best.snd;
}
