#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long n,a[100069],fw[100069],fi,pr[200069][18],sr[100069],sp[17][100069],lg2[100069];
pair<long long,long long> rg[100069];
void ud(long long x,long long w)
{
for(fi=x;fi<=n;fi+=fi&-fi)
{
fw[fi]+=w;
}
}
long long bl(long long x)
{
long long i,sm=0;
fi=0;
for(i=16;i+1;i--)
{
if((fi|1ll<<i)<=n&&sm+fw[fi|1ll<<i]<x)
{
fi|=1ll<<i;
sm+=fw[fi];
}
}
return fi+!!x;
}
void spbd()
{
long long i,j,k;
for(i=1;1ll<<i<n;i++)
{
for(j=1;j<n-(1ll<<i)+1;j++)
{
sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
}
}
for(i=1;i<n;i++)
{
for(k=i;k>1;k/=2,lg2[i]++);
}
}
long long spqr(long long lh,long long rh)
{
long long e=lg2[rh-lh+1];
return max(sp[e][lh],sp[e][rh-(1ll<<e)+1]);
}
int GetBestPosition(int on,int m,int d,int *aa,int *ka,int *la)
{
long long i,j,k,l,p,lh,rh,md,zz,sm,e;
pair<long long,long long> z={-1,-1};
n=on;
d++;
for(i=1;i<n;i++)
{
a[i]=aa[i-1]+1;
sp[0][i]=a[i];
}
for(i=1;i<=n;i++)
{
ud(i,1);
sr[i]=i;
}
for(i=1;i<=m;i++)
{
k=ka[i-1]+1;
l=la[i-1]+1;
for(j=l;j>=k;j--)
{
p=bl(j);
if(j<l)
{
ud(p,-1);
}
pr[sr[p]][0]=n+i;
}
p=bl(k);
rg[i]={bl(k-1)+1,p};
sr[p]=n+i;
}
for(i=n+m;i;i--)
{
for(j=1;j<18;j++)
{
pr[i][j]=pr[pr[i][j-1]][j-1];
}
}
spbd();
for(i=1;i<=n;i++)
{
for(zz=i,lh=1,rh=i-1;lh<=rh;)
{
md=(lh+rh)/2;
if(spqr(md,i-1)<d)
{
zz=md;
rh=md-1;
}
else
{
lh=md+1;
}
}
k=zz;
for(zz=i-1,lh=i,rh=n-1;lh<=rh;)
{
md=(lh+rh)/2;
if(spqr(i,md)<d)
{
zz=md;
lh=md+1;
}
else
{
rh=md-1;
}
}
l=zz+1;
sm=0;
p=i;
for(j=17;j+1;j--)
{
if(pr[p][j]&&rg[pr[p][j]-n].fr>=k&&rg[pr[p][j]-n].sc<=l)
{
sm|=1ll<<j;
p=pr[p][j];
}
}
z=max(z,{sm,-i});
}
e=-z.sc;
return e-1;
}
