短調非増加の答えでの値Kの範囲

int test(mid) の関数をあらかじめ作っておく必要がある

bs(k) = 答えがkになる範囲の{L,R}をpairで返す

pair<int,int> bs(int k){

    int big,small;
    int l = 0;
    int r = INF;
    while(l+1 < r){    // find big
        int mid = (l+r)/2;
        int res = test(mid);
        if(res >= k){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    big = l;
    l = 0;
    r = INF;
    while(l+1 < r){    // find small
        int mid = (l+r)/2;
        int res = test(mid);
        if(res > k){
            l = mid;
        }
        else{
            r = mid;
        }
    }    
    small = r;
    return {small,big};
}