def bisect(a, x, lo=0, hi=None, cmp=lambda e1, e2: e1 < e2):
    """
    a simplified and generalized version of python's bisect package: https://docs.python.org/3.6/library/bisect.html

    return the index where to insert item x in a list a
    a must be sorted (in ascending order)
    the return value i is such that:
    1. all e in a[:i] have: cmp(e, x)
    2. all e in a[i:] have: not cmp(e, x)
    if cmp is set to <=, the function goes for the rightmost position;
    if cmp is set to <, the function goes for the leftmost position.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if cmp(a[mid], x):
            lo = mid + 1
        else:
            hi = mid
    return lo