#include <bits/stdc++.h>

using namespace std;
const int N = 6;
int a[N] = {1, 2, 2, 3, 3, 4};

//模拟STL中的lower_bound,左闭右开写法
// int lower_bound(int x) {
//     int l = 0, r = 7; //左闭右开
//     while (l <= r) {
//         int mid = (l + r) >> 1;
//         if (x > a[mid])
//             l = mid + 1;
//         else
//             r = mid - 1;
//     }
//     return l;
// }

int upper_bound(int x) {
    int l = 0, r = N;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (x >= a[mid]) // upper的话等于的时候也返                          //回右边,因为要找到大于最后一个key。
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l; //记得返回L。
}

int lower_bound(int x) {
    int l = 0, r = N;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (x > a[mid])
            l = mid + 1;
        else // lower相等时候就返回左边，因为要
             //找到第一个key。
            r = mid - 1;
    }
    return l;
}

int main() {
    printf("%d\n", lower_bound(3));
    printf("%d\n", upper_bound(3) - 1);

    printf("%d\n", lower_bound(4));
    printf("%d\n", upper_bound(4) - 1);

    printf("%d\n", lower_bound(5));
    printf("%d\n", upper_bound(5) - 1);
    return 0;
}