#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,R,f[100009],seg[400009],seg2[400009],l,r,z,za,Z,msh[400009],cnt,mx[400009],ans[400009],LE[400009],RI[400009],SEG[400009];
vector <int> v[400009];
set <pair <int, int> > s;
set <pair <int, int> >::iterator it,tt;
void READ(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=max(z,SEG[rr]);
return;
}
READ(q,(q+w)/2,rr*2);
READ((q+w)/2+1,w,rr*2+1);
}
void pushdown(int q, int w, int rr){
if(q!=w){
seg2[rr*2]+=seg2[rr];
seg2[rr*2+1]+=seg2[rr];
}
seg[rr]+=seg2[rr];
seg2[rr]=0;
}
void upd(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
seg2[rr]=z;
pushdown(q,w,rr);
return;
}
upd(q,(q+w)/2,rr*2);
upd((q+w)/2+1,w,rr*2+1);
seg[rr]=max(seg[rr*2],seg[rr*2+1]);
}
void read(int q, int w, int rr){
if(q==w){
z=q;
return;
}
pushdown(q,(q+w)/2,rr*2);
pushdown((q+w)/2+1,w,rr*2+1);
if(seg[rr*2]<Z){
read((q+w)/2+1,w,rr*2+1);
}else{
read(q,(q+w)/2,rr*2);
}
}
void dfs(int q, int w){
l=LE[q];r=RI[q]-1;z=0;
if(l<=r){
READ(1,za,1);
mx[q]=z;
}
if(q<=a){
//mx[q]=f[q];
return;
}
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
dfs((*it),q);
//mx[q]=max(mx[q],mx[(*it)]);
}
}
void dfs2(int q, int w, int rr){
if(q<=a){
ans[q]=rr-1;
return;
}
if(mx[q]>R) rr=0;
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it)==w) continue;
dfs2((*it),q,rr+1);
}
}
int GetBestPosition(int NN, int CC, int RR, int *KK, int *SS, int *EE) {
a=NN;tes=CC;R=RR;R++;
for(i=1; i<a; i++){
f[i]=KK[i-/*2*/1];f[i]++;
}
za=1;
while(za<a) za*=2;
for(i=1; i<a; i++){
SEG[za+i-1]=f[i];
}
for(i=za-1; i>=1; i--){
SEG[i]=max(SEG[i*2],SEG[i*2+1]);
}
for(i=1; i<=a; i++){
s.insert({i,i});
l=i;r=za;z=1;
upd(1,za,1);
}
cnt=a;
for(i=1; i<=a; i++){
LE[i]=RI[i]=i;
}
/*for(t=1; t<=tes; t++){
c=SS[t-1]+1;d=EE[t-1]+1;
Z=c;z=0;
pushdown(1,za,1);
read(1,za,1);
e=z;
//cout<<"tes: "<<t<<" "<<e<<"\n";
//if(t==3) return 0;
it=s.lower_bound({e,0});
zx=d-c+1;cnt++;
LE[cnt]=LE[(*it).second];RI[cnt]=RI[(*it).second];
while(zx>0){
zx--;
msh[(*it).second]=cnt;
v[cnt].push_back((*it).second);
l=(*it).first;r=za;z=-1;
read(1,za,1);
tt=it;tt++;
RI[cnt]=RI[(*it).second];
s.erase(it);
it=tt;
}
s.insert({e,cnt});
l=e;r=za;z=1;
upd(1,za,1);
}*/
for(t=1; t<=tes; t++){
c=SS[t-1]+1;d=EE[t-1]+1;
int ER=0;
cnt++;
LE[cnt]=RI[cnt]=-2;
for(it=s.begin(); it!=s.end(); ){
ER++;
if(ER<c||ER>d){
it++;
continue;
}
tt=it;tt++;
if(LE[cnt]==-2){
LE[cnt]=LE[(*it).second];
}
RI[cnt]=RI[(*it).second];
msh[(*it).second]=cnt;
v[cnt].push_back((*it).second);
s.erase(it);
it=tt;
}
s.insert({LE[cnt],cnt});
}
/*for(i=1; i<=cnt; i++){
cout<<i<<" "<<msh[i]<<"\n";
}
for(i=1; i<=a; i++) cout<<f[i]<<" ";
cout<<"\n";*/
dfs(cnt,0);
dfs2(cnt,0,1);
zx=-1;xc=0;
for(i=1; i<=a; i++){
//zx=max(zx,ans[i]);
if(zx<ans[i]){
zx=ans[i];xc=i;
}
}
return xc-1;
}
