#include <bits/stdc++.h>
using namespace std;
const int sz=262144;
int seg[sz*2];
int pos[200000];
int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
if (r<nodel||l>noder) {
return 0;
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder);
}
void update(int i,int val) {
i+=sz;
seg[i]+=val;
while (i>1) {
i/=2;
seg[i]=seg[i*2]+seg[i*2+1];
}
}
int find(int k,int node=1) {
if (node>=sz) {
return node-sz;
}
if (seg[node*2]>k) {
return find(k,node*2);
}
else {
return find(k-seg[node*2],node*2+1);
}
}
vector<int> son[200000];
int cnt;
int f=0;
int ind[200000];
int par[200000][18];
int sub[200000];
void dfs(int v) {
ind[v]=f++;
sub[v]=1;
for(int i=0;i<son[v].size();i++) {
dfs(son[v][i]);
sub[v]+=sub[son[v][i]];
}
}
int GetBestPosition(int n,int c,int r,int *K, int *S, int *E) {
for(int i=0;i<n;i++) {
pos[i]=i;
update(i,1);
}
cnt=n;
memset(par,-1,sizeof(par));
for(int i=0;i<c;i++) {
int now=find(S[i]);
int save=pos[now];
pos[now]=cnt++;
son[pos[now]].push_back(save);
par[save][0]=pos[now];
for(int j=S[i]+1;j<=E[i];j++) {
int got=find(S[i]+1);
son[pos[now]].push_back(pos[got]);
par[pos[got]][0]=pos[now];
update(got,-1);
}
}
for(int j=1;j<18;j++) {
for(int i=0;i<n;i++) {
if (par[i][j-1]!=-1) {
par[i][j]=par[par[i][j-1]][j-1];
}
}
}
memset(seg,0,sizeof(seg));
dfs(cnt-1);
for(int i=0;i<n-1;i++) {
if (K[i]>r) {
update(ind[i+1],1);
}
}
int mx=-1;
int ret=-1;
for(int pos=0;pos<n;pos++) {
int now=pos;
int val=0;
for(int i=17;i>=0;i--) {
int nt=par[now][i];
if (nt==-1) {
continue;
}
if (sum(ind[nt],ind[nt]+sub[nt]-1)==0) {
now=nt;
val+=(1<<i);
}
}
if (val>mx) {
ret=pos;
mx=val;
}
if (pos!=n-1) {
if (K[pos]>r) {
update(ind[pos+1],-1);
update(ind[pos],1);
}
}
}
return ret;
}
