Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:                 for i = 1 to A.length-1     key = A[i]     /* insert A[i] into the sorted sequence A[0,...,j-1] */     j = i - 1     while j >= 0 and A[j] > key         A[j+1] = A[j]         j--     A[j+1] = key   Note that, indices for array elements are based on 0-origin.  To illustrate the algorithms, your program should trace intermediate result for each step.
def insertionSort(lst, n):
    for i in range(1, n):
        v = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > v:
            lst[j+1] = lst[j]
            j = j - 1
        lst[j+1] = v
        print(lst)


if __name__ == "__main__":
    n = int(input())
    lst = [int(n) for n in input().split()]
    print(lst)
    insertionSort(lst, n)
def insertionSort(lst, n):
    print(" ".join([str(n) for n in lst]))
    for i in range(1, n):
        v = lst[i]
        for j in range(0, i):
            if lst[j] > v:
                lst.insert(j, lst.pop(i))
                break

        print(" ".join([str(n) for n in lst]))

    return lst


if __name__ == "__main__":
    n = int(input())
    lst = [int(n) for n in input().split()]
    insertionSort(lst, n)