def do_insertions_simple(l, insertions):
    r = list(l)
    for i, x in insertions:
        r.insert(i, x)
    return r


def do_insertions_fast(l, insertions):
    result = []
    extended = 0
    for appended, (idx, val) in enumerate(insertions):
        if idx > len(result):
            result.extend(l[extended : idx - appended])
            extended += idx - appended - extended
        result.append(val)
    result.extend(l[extended:])
    return result


from random import randint

l = list(range(1_000_000))
insertions = [(randint(0, len(l)), "x") for _ in range(10_000)]
insertions.sort()
r1 = do_insertions_simple(l, insertions)
r2 = do_insertions_fast(l, insertions)
assert r1 == r2