#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],g[100009];
vector <int> v[400009];
set <pair <int, int> > s;
set <pair <int, int> >::iterator it,tt;
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){
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(mx[q]>R) rr=0;
if(q<=a){
ans[q]=rr-1;
return;
}
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=2; i<=a; i++){
f[i]=KK[i-2];f[i]++;
}
for(i=1; i<a; i++){
g[i]=f[i+1];
}
zx=-1;xc=-1;
for(ii=1; ii<=a; ii++){
for(i=1; i<=a; i++){
if(i<ii){
f[i]=g[i];
continue;
}
if(i==ii){
f[i]=R;
continue;
}
f[i]=g[i-1];
}
e=0;
for(t=1; t<=tes; t++){
c=SS[t-1]+1;d=EE[t-1]+1;
int mx1=0,mx2=0,E=0;
for(i=c; i<=d; i++){
if(f[i]==R) E=1;
if(mx1<f[i]){
mx1=f[i];mx2=i;
}
}
if(E==1){
if(mx1==R){
e++;
}else{
break;
}
}
f[c]=f[mx2];
for(i=c+1; ; i++){
j=i+(d-c);
if(f[j]==0) break;
f[i]=f[j];
}
}
if(zx<e){
zx=e;xc=ii;
}
}
return xc-1;
}
