int gmax(register int a,register int b){return a>b?a:b;}
int gmin(register int a,register int b){return a<b?a:b;}
int binary_search(unsigned *a,int n,register unsigned x)
{
n--;
int p=1ll*n*(x-a[0])/(a[n]-a[0]+1),lim=16;
p+=1ll*(n-p)*(x-a[p])/(a[n]-a[p]+1);
//p+=1ll*(n-p)*(x-a[p])/(a[n]-a[p]+1);
if(x<=a[p])
{
for(;a[gmax(p-lim,0)]>x;lim<<=1);
register int l=gmax(p-lim,0),r=p;
do
{
register int mid=(l+r)>>1;
(a[mid]<x)?(l=mid+1):(r=mid);
}
while(l!=r);
return l;
}
else
{
for(;x>a[gmin(p+lim,n)];lim<<=1);
register int l=p,r=gmin(p+lim,n);
do
{
register int mid=(l+r)>>1;
(a[mid]<x)?(l=mid+1):(r=mid);
}
while(l!=r);
return l;
}
}