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())
line=input().split()
A=[0]*N
for i in range(0,N):
    A[i]=int(line[i])
for i in range(N):
    v=A[i]
    j=i-1
    while j>=0 and A[j]>v:
        A[j+1]=A[j]
        j-=1
        A[j+1]=v
    print(A)


N=int(input())
line=input().split()
A=[0]*N
for i in range(0,N):
    A[i]=int(line[i])
for i in range(N):
    """
    for k in range(N):
        print(A[k],end="")
        if k==N-1:
            print()
        else:
            print(" ",end="")
    """
    v=A[i]
    j=i-1
    while j>=0 and A[j]>v:
        A[j+1]=A[j]
        j-=1
        A[j+1]=v
    for k in range(N):
        print(A[k],end="")
        if k==N-1:
            print()
        else:
            print(" ",end="")

