#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <limits>
#include <vector>

std::size_t lower_index(const std::vector<int>& a, int target) {
    std::size_t left = 0, right = a.size();
    while (left < right) {
        const std::size_t mid = left + (right - left) / 2;
        if (a[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

std::size_t upper_index(const std::vector<int>& a, int target) {
    std::size_t left = 0, right = a.size();
    while (left < right) {
        const std::size_t mid = left + (right - left) / 2;
        if (a[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;
}

void check(const std::vector<int>& a) {
    assert(std::is_sorted(a.begin(), a.end()));
    const int targets[] = {
        std::numeric_limits<int>::min(), -3, -2, -1, 0, 1, 2, 3,
        std::numeric_limits<int>::max()
    };
    for (int x : targets) {
        const auto lo = lower_index(a, x);
        const auto hi = upper_index(a, x);
        const auto expected_lo = static_cast<std::size_t>(
            std::lower_bound(a.begin(), a.end(), x) - a.begin());
        const auto expected_hi = static_cast<std::size_t>(
            std::upper_bound(a.begin(), a.end(), x) - a.begin());
        assert(lo == expected_lo && hi == expected_hi);
        assert(lo <= hi && hi <= a.size());
        assert(lo == 0 || a[lo - 1] < x);
        assert(lo == a.size() || a[lo] >= x);
        assert(hi == 0 || a[hi - 1] <= x);
        assert(hi == a.size() || a[hi] > x);
    }
}

// Enumerate every nondecreasing sequence of length <= remaining
// over the alphabet [minimum, 2].
void enumerate(std::vector<int>& a, std::size_t remaining, int minimum) {
    check(a);
    if (remaining == 0) return;
    for (int value = minimum; value <= 2; ++value) {
        a.push_back(value);
        enumerate(a, remaining - 1, value);
        a.pop_back();
    }
}

int main() {
    std::vector<int> a;
    enumerate(a, 6, -2);
    const std::vector<int> extremes = {
        std::numeric_limits<int>::min(),
        std::numeric_limits<int>::min(), 0,
        std::numeric_limits<int>::max()
    };
    check(extremes);
    const std::vector<int> same = {7, 7, 7};
    assert(lower_index(same, 7) == 0);
    assert(upper_index(same, 7) == same.size());
    assert(lower_index(same, 8) == same.size());
    std::cout << "binary boundaries: all assertions passed\n";
}