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)
{
register unsigned*p=a+1ll*n*x/a[n-1];
if(x<=*p)
{
for(register int t=32768;t;t>>=1)p[-t]>=x?p-=t:0;
return p-a;
}
else
{
for(register int t=32768;t;t>>=1)p[t]<=x?p+=t:0;
return p-a;
}
}