bisection algorithms def insortrighta x lo0 hinone keynone if key is none lo bisectrighta x lo hi else lo bisectrighta keyx lo hi keykey a insertlo x def bisectrighta x lo0 hinone keynone if lo 0 raise valueerror lo must be nonnegative if hi is none hi lena note the comparison uses to match the lt logic in list sort and in heapq if key is none while lo hi mid lo hi 2 if x amid hi mid else lo mid 1 else while lo hi mid lo hi 2 if x keyamid hi mid else lo mid 1 return lo def insortlefta x lo0 hinone keynone if key is none lo bisectlefta x lo hi else lo bisectlefta keyx lo hi keykey a insertlo x def bisectlefta x lo0 hinone keynone if lo 0 raise valueerror lo must be nonnegative if hi is none hi lena note the comparison uses to match the lt logic in list sort and in heapq if key is none while lo hi mid lo hi 2 if amid x lo mid 1 else hi mid else while lo hi mid lo hi 2 if keyamid x lo mid 1 else hi mid return lo overwrite above definitions with a fast c implementation try from bisect import except importerror pass create aliases bisect bisectright insort insortright insert item x in list a and keep it sorted assuming a is sorted if x is already in a insert it to the right of the rightmost x optional args lo default 0 and hi default len a bound the slice of a to be searched a custom key function can be supplied to customize the sort order return the index where to insert item x in list a assuming a is sorted the return value i is such that all e in a i have e x and all e in a i have e x so if x already appears in the list a insert i x will insert just after the rightmost x already there optional args lo default 0 and hi default len a bound the slice of a to be searched a custom key function can be supplied to customize the sort order note the comparison uses to match the __lt__ logic in list sort and in heapq insert item x in list a and keep it sorted assuming a is sorted if x is already in a insert it to the left of the leftmost x optional args lo default 0 and hi default len a bound the slice of a to be searched a custom key function can be supplied to customize the sort order return the index where to insert item x in list a assuming a is sorted the return value i is such that all e in a i have e x and all e in a i have e x so if x already appears in the list a insert i x will insert just before the leftmost x already there optional args lo default 0 and hi default len a bound the slice of a to be searched a custom key function can be supplied to customize the sort order note the comparison uses to match the __lt__ logic in list sort and in heapq overwrite above definitions with a fast c implementation create aliases
def insort_right(a, x, lo=0, hi=None, *, key=None):
    
    if key is None:
        lo = bisect_right(a, x, lo, hi)
    else:
        lo = bisect_right(a, key(x), lo, hi, key=key)
    a.insert(lo, x)


def bisect_right(a, x, lo=0, hi=None, *, key=None):
    

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    
    
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < a[mid]:
                hi = mid
            else:
                lo = mid + 1
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < key(a[mid]):
                hi = mid
            else:
                lo = mid + 1
    return lo


def insort_left(a, x, lo=0, hi=None, *, key=None):
    

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)

def bisect_left(a, x, lo=0, hi=None, *, key=None):
    

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    
    
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo



try:
    from _bisect import *
except ImportError:
    pass


bisect = bisect_right
insort = insort_right