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.
n = int(input())
x = input().split()
y=[]
for i in range(n):
    y += [int(x[i])]
print(y)

for i in range(1,n):
    v = y[i]
    j = i-1
    while j >= 0 and y[j] > v:
        y[j+1] = y[j]
        j -= 1
    y[j+1] = v
    print(y)


n = int(input())
x = input().split()
y=[]
for i in range(n):
    y += [int(x[i])]
for i in range(n-1):
    print(y[i],end=' ')
print(y[n-1])

for i in range(1,n):
    v = y[i]
    j = i-1
    while j >= 0 and y[j] > v:
        y[j+1] = y[j]
        j -= 1
    y[j+1] = v
    for j in range(n-1):
        print(y[j],end=' ')
    print(y[n-1])

