binary

int lower_bound(int n)
{
    int l=0,r=n;
    int cnt=r-l;
    while (cnt>0)
    {
        int it=l,st=cnt>>1;
        it+=st;
        if (check(it))
        {
            l=it+1;
            cnt-=st+1;
        } else
            cnt=st;
    }
    return l;
}