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())
a=list(map(int, input().split()))
k=list(str(a))
j='  '.join(k)
print(j)
for i in range(1,N):
    v=a[i]
    j=i-1
    while a[j]>v and j>=0:
        a[j+1]=a[j]
        j -=1
    a[j+1]=v
    b=a[:]
    c='  '.join(str(b))
    print(c)
  

N=int(input())
a=list(map(int, input().split()))
k=list(map(str,a))
j=' '.join(k)
print(j)
for i in range(1,N):
    v=a[i]
    j=i-1
    while a[j]>v and j>=0:
        a[j+1]=a[j]
        j -=1
    a[j+1]=v
    b=list(map(str, a))
    c=' '.join(b)
    print(c)
