//整数二分的板子，记住左侧的用对称写右边的
//a[n]是下标从1开始的单调不减序列；
//查找最后一个小于等于q的数的下标：可行化区域在左侧；
int find(int q){

    int l=0,r=n+1;//初始时，左右指针分别在数组的左右各一个单位，行成开区间

    while(l+1<r)//当l+1==r时终止，如此可保证l始终在可行区域内
    {
        int mid = (l+r)>>1; 
        if(a[mid] <= q)  l=mid; //mid仍有可能是q,因此更新左边界为mid，防止遗漏答案;
        else r=mid;             //
    }
    return l;
}

//查找第一个大于等于q的数的下标，可行区域在右侧
int  find(int q)
{
    int l=0,r=n+1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(a[mid] >= q) r=mid;  //对称写法
        else l=mid;             //对称
    }
    return r;   //对称
}