import bisect


def leftmostBinSearch(vec, val):
    """
    Return the leftmost position in the vector vec of val. If val is
    absent then we return the lefternmost position for the value:
    max(vec[vec < val]). The time complexity here is potentially worse
    than log(n) because of the extra step of walking backwards.
    """
    assert(len(vec) > 0)
    i = bisect.bisect_left(vec, val)

    if (i == 0):
        return(i)
    elif (i == len(vec)):
        v = vec[i-1]
        i -= 1
    else:
        v = vec[i]

    if (v > val):
        i -= 1

    while (i > 0 and vec[i-1] == vec[i]):
        i -= 1

    return(i)