"""Tìm vị trí chèn đầu tiên trong một dãy đã sắp không giảm."""
from bisect import bisect_left
from itertools import combinations_with_replacement


def vi_tri_chen(danh_sach, khoa):
    lo, hi = 0, len(danh_sach)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if danh_sach[mid] < khoa:
            lo = mid + 1
        else:
            hi = mid
    return lo


def tim_lan_dau(danh_sach, khoa):
    i = vi_tri_chen(danh_sach, khoa)
    return i if i < len(danh_sach) and danh_sach[i] == khoa else -1


if __name__ == "__main__":
    a = [1, 3, 3, 5]
    for khoa in (0, 3, 4, 6):
        print(khoa, "vị trí chèn:", vi_tri_chen(a, khoa),
              "| vị trí xuất hiện:", tim_lan_dau(a, khoa))

    so_ca = 0
    for n in range(6):
        for day in combinations_with_replacement(range(-2, 3), n):
            for khoa in range(-3, 4):
                expected = bisect_left(day, khoa)
                assert vi_tri_chen(day, khoa) == expected
                assert tim_lan_dau(day, khoa) == next(
                    (i for i, value in enumerate(day) if value == khoa), -1
                )
                so_ca += 1
    print("Đã đối chiếu", so_ca, "ca.")