def bisect_func_left(x, lo, hi, func):
    """Bisect `func(i)`, returning an index such that preceding values are less
    than `x`. If `x` is present, the returned index is its first occurrence.
    EOF is assumed if `func` returns None."""
    while lo < hi:
        mid = (lo + hi) // 2
        k = func(mid)
        if k is not None and k < x:
            lo = mid + 1
        else:
            hi = mid
    return lo
