Problem:
Insertion Sort 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. Input The first line of the input includes an integer N, the number of elements in the sequence. In the second line, N elements of the sequence are given separated by a single space. Output The output consists of N lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space. Constraints 1 ≤ N ≤ 100 Sample Input 1 6
5 2 4 6 1 3 Sample Output 1 5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6 Sample Input 2 3
1 2 3 Sample Output 2 1 2 3
1 2 3
1 2 3 Hint Template in C

Solution (Python):
def insertion_sort(A):
    for i in range(1,len(A)):
        print(*A)
        key = A[i]
        
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]
            j-=1
        A[j+1] = key
 
if __name__=='__main__':
   n=int(input()) 
   A=list(map(int,input().split()))
   insertion_sort(A)
   print(*A)

Solution (Python):
N = int(input())
A= list(map(int, input().split()))
print(" ".join(map(str, A)))
for i in range(1, 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(" ".join(map(str, A)))

Solution (Python):
num_inputs = int(input())
input_array = input().split(' ')

for i in range(1, num_inputs):
    print(' '.join(input_array))
    current_value = input_array[i]
    j = i - 1
    while j >= 0 and int(input_array[j]) > int(current_value):
        input_array[j + 1] = input_array[j]
        j -= 1
    input_array[j + 1] = current_value
    
print(' '.join(input_array))

Solution (Python):
def show (nums):
    for i in range(len(nums)):
        if i!=len(nums)-1:
            print(nums[i],end=' ')
        else :
            print(nums[i])
 
n=int(input())
nums=list(map(int,input().split()))
show(nums)
for i in range(1,n):
    v=nums[i]
    j=i-1
    while (j>=0 and nums[j]>v):
        nums[j+1]=nums[j]
        j-=1
    nums[j+1]=v
    show(nums)

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
def convert(list):
    s=[str(i) for i in list]
    res = " ".join(s)
    return res
print(convert(A))
for i in range(1,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(convert(A))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
for i in range(0,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(" ".join(map(str,a)))

Solution (Python):
def show (nums):
    for i in range(len(nums)):
        if i!=len(nums)-1:
            print(nums[i],end=' ')
        else :
            print(nums[i])
 
n=int(input())
nums=list(map(int,input().split()))
show(nums)
for i in range(1,n):
    v=nums[i]
    j=i-1
    while (j>=0 and nums[j]>v):
        nums[j+1]=nums[j]
        j-=1
    nums[j+1]=v
    show(nums)

Solution (Python):
n = int(input())
A = list(map(int,input().split(" ")))


def fun(n,A):
    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(" ".join(["{0["+ str(i) + "]}" for i in range(n)]).format(A))

fun(n,A)

Solution (Python):
def show (nums):
    for i in range(len(nums)):
        if i!=len(nums)-1:
            print(nums[i],end=' ')
        else :
            print(nums[i])
 
n=int(input())
nums=list(map(int,input().split()))
show(nums)
for i in range(1,n):
    v=nums[i]
    j=i-1
    while (j>=0 and nums[j]>v):
        nums[j+1]=nums[j]
        j-=1
    nums[j+1]=v
    show(nums)

Solution (Python):
n = int(input())
nums = list(map(int, input().split()))
print(' '.join(map(str, nums)))

for i in range(1, n):
    key = nums[i]
    j = i - 1
    while j >= 0 and nums[j] > key:
        nums[j + 1] = nums[j]
        j -= 1
    nums[j + 1] = key
    print(' '.join(map(str, nums)))

Solution (Python):
n = int(input())

A = [int(s) for s in input().split()]
print(*A)

for i in range(1, n):
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        j -= 1
    A.insert(j+1, key)
    del A[i+1]

    print(*A)

Solution (Python):
N = int(input())
A= list(map(int, input().split()))
print(" ".join(map(str, A)))
for i in range(1, 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(" ".join(map(str, A)))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

print(' '.join(map(str, A)))

for i in range(1, N):
  v = A[i]
  j = i - 1
  while j >= 0 and A[j] > v:
    A[j], A[j+1] = A[j+1], A[j]
    j -= 1
  print(' '.join(map(str, A)))

Solution (Python):
def show (nums):
    for i in range(len(nums)):
        if i!=len(nums)-1:
            print(nums[i],end=' ')
        else :
            print(nums[i])
 
n=int(input())
nums=list(map(int,input().split()))
show(nums)
for i in range(1,n):
    v=nums[i]
    j=i-1
    while (j>=0 and nums[j]>v):
        nums[j+1]=nums[j]
        j-=1
    nums[j+1]=v
    show(nums)

Solution (Python):
def sort(a, n):
	print(" ".join(map(str, a)))
	for i in range(1, N):
		v = a[i]
		j = i - 1
		while 0 <= j and v < a[j]:
			a[j + 1] = a[j]
			j -= 1
		a[j + 1] = v
		print(" ".join(map(str, a)))

N = int(input())
A = list(map(int, input().split()))

sort(A, N)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
for j in range(n):
  print(a[j], end="")
  if j < n-1:
    print(" ", end="")
  else:
    print("")

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

  for j in range(n):
    print(a[j], end="")
    if j < n-1:
      print(" ", end="")
    else:
      print("")

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
print(*a, sep=' ')

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

Solution (Python):
n = int(input())
*A, = map(int, input().split())
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)

Solution (Python):
def insertitionSort(A,N):
    for i in range(N):
        v = A[i]
        j = i -1
        
        while j>=0 and A[j] > v:
            A[j+1] = A[j]
            j = j -1
        A[j+1] = v
        map_result = map(str, A)
        print(' '.join(map_result))                  


N = int(input())
A = list(map(int, input().split()))   

insertitionSort(A,N)

Solution (Python):
def insertionSort(A, N):
    for i in range(1, N):
        print(' '.join(map(lambda x: str(x), A)))
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
    return A

N = int(input())
A = list(map(int, input().split()))
A = insertionSort(A, N)

print(' '.join(map(lambda x: str(x), A)))

Solution (Python):
N=int(input())
number=list(map(int,input().split()))

print(' '.join(map(str,number)))
for i in range(1,N):
    strage=number[i]
    j=i-1
    for j in range(0,i)[::-1]:
        if number[j]>strage:
            number[j+1]=number[j]
            j-=1
            number[j+1]=strage
    print(' '.join(map(str,number)))

Solution (Python):
n = int(input())
alist = list(map(int, input().split()))

print(" ".join([str(i) for i in alist]))

def insertion_sort(alist, n):
    for i in range(1, n):
        current = alist[i]
        j = i - 1
        while j >= 0 and alist[j] > current:
            alist[j], alist[j+1] = alist[j+1], alist[j]
            j -= 1
        print(" ".join([str(i) for i in alist]))

insertion_sort(alist, n)

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
print(*A)
for i in range(1,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)

Solution (Python):
num = int(input())
num_array = input().split(" ")

for i in range(num):
    num_array[i] = int(num_array[i])


def put_array():
    for i in range(num):
        print(num_array[i], end="")
        if i != num-1:
            print(" ", end="")
        else:
            print("")

def insertionSort(A, N):
    for i in range(1, N):
        put_array()
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v


if __name__ == "__main__":

    insertionSort(num_array, num)

    put_array()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
print(" ".join(list(map(str, A))))
for i in range(1, 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(" ".join(list(map(str, A))))

Solution (Python):
N = int(input())
A = input().split()
A = [int(i) for i in A]


def print_list_val(A):
    s = ''
    for i in range(len(A)):
        s = s + str(A[i])
        if i != len(A) - 1:
            s += " "
    print(s)
    
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_list_val(A)

Solution (Python):
def insertionSort(A, N):
    for i in range(N):
        s = ""
        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(' '.join(map(str, A)))
            
if __name__ == '__main__':
    N = int(input()) 
    M = list(map(int,input().split()))
    insertionSort(M, N)

Solution (Python):






import sys
import math


class mymath:
    
    pi = 3.14159265358979323846264338

    
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans

mymath = mymath()


class output:
    
    def list(self, l):
        l = list(l)
        
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()































def get_input():
    N = []
    while True:
        try:
            N.append(input())
            
            
        except EOFError:
            break
    return N

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

def dist(A, B):
    d = 0
    for i in range(len(A)):
        d += (A[i]-B[i])**2            
    d = d**(1/2)
    return d


N = int(input())
A = [int(x) for x in input().split()]



def printA(A):
    for i, n in enumerate(A):
        print(n, end='')
        if i != N-1:
            print(' ', end='')
    print()

printA(A)

count = 0
for i in range(1, 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
    printA(A)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

def insertionSort(A, N):
    for i in range(N-1):
        print(' '.join(repr(e) for e in A))
        v = A[i+1]
        j = i
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
            A[j+1] = v
    print(' '.join(repr(e) for e in A))

insertionSort(A, N)

Solution (Python):
def show(A):
    L = list(map(str, A))
    print(" ".join(L))

N = int(input())
A = list(map(int, input().split()))

show(A)

for i in range(1, 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
    
    show(A)

Solution (Python):
if __name__=='__main__':
    N = int(input())
    A = [ int(_) for _ in input().split(' ') ]
    print(' '.join(map(str,A)))
    for i in range(1, N):
        key = A[i]
        j = i-1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = key
        print(' '.join(map(str,A)))

Solution (Python):
if __name__ == "__main__":
    elem_num = int(input())
    elems = list(map(lambda x: int(x), input().split()))
    print(" ".join([str(elem) for elem in elems]))  
    for i in range(1, elem_num):
        key = elems[i]
        j = i - 1
        while j >= 0 and elems[j] > key:
            elems[j + 1] = elems[j]
            j -= 1
        elems[j + 1] = key
        print(" ".join([str(elem) for elem in elems]))

Solution (Python):
def insertionSort(A, N):
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1], A[j] = A[j], A[j+1]
            j -= 1
        print(' '.join(map(str, A)))


N = int(input())
A = list(map(int, input().split()))
print(' '.join(map(str, A)))
insertionSort(A, N)

Solution (Python):
def insertion_sort(A):
    for i in range(1,len(A)):
        print(*A)
        key = A[i]
        
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]
            j-=1
        A[j+1] = key
 
if __name__=='__main__':
   n=int(input()) 
   A=list(map(int,input().split()))
   insertion_sort(A)
   print(*A)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
print(" ".join(list(map(str, A))))
for i in range(1, 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(" ".join(list(map(str, A))))

Solution (Python):


def main():
    n = int(input())
    array = [int(i) for i in input().split(' ')]
    my_print(array)
    for i in range(1, n):
        target = array[i]

        j = i - 1
        while target < array[j] and j >= 0:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = target
        my_print(array)


def my_print(array):
    print(' '.join(map(str, array)))


if __name__ == '__main__':
    main()

Solution (Python):
def insertionSort(a, n):
    for i in range(1, 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(" ".join(map(str, a)))

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    print(" ".join(map(str, a)))
    insertionSort(a, n)

Solution (Python):
n=int(input())
a =list(map(int,input().split()))



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(' '.join(map(str,a)))

Solution (Python):

def insertion_sort(arr):
    for i in range(1, len(arr)):
        temp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > temp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = temp
        print(' '.join(map(str, arr)))

if __name__ == '__main__':
    N = int(input())
    arr = [int(n) for n in input().split()]
    print(' '.join(map(str, arr)))
    insertion_sort(arr)

Solution (Python):
if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    for x in A:
        print x,
    print
    for i in range(1, 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

        for x in A:
            print x,
        print

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]

def insertion_sort(A, N):
    print(' '.join(str(_) for _ in A))
    for i in range(1, 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(' '.join(str(_) for _ in A))

insertion_sort(A, N)

Solution (Python):
def insert_sort(n, nums):
    for i in range(1, n):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = key
        print(' '.join(map(str, nums)))


n = int(input())
nums = list(map(int, input().split()))

print(' '.join(map(str, nums)))
insert_sort(n, nums)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
s = " ".join(map(str, a))
print(s)
for i in range(1, 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
    s = " ".join(map(str, a))
    print(s)

Solution (Python):
N = int(input())

A = []

nums = input().split()

for i in range(N):
    A.append(int(nums[i]))

l = [str(i) for i in A]
print(" ".join(l))
    
for i in range(1, 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
    l = [str(i) for i in A]
    print(" ".join(l))

Solution (Python):
def p(a):
    for i in a[:-1]:
        print(i,end=' ')
    print(a[-1])


def insertion_sort(a):
    for i in range(1,len(a)):
        p(a)
        d = a[i]
        j = i-1
        while j>=0 and d<a[j]:
            a[j+1] = a[j]
            j = j-1
        a[j+1] = d


n = int(input())
l = list(map(int,input().split()))
insertion_sort(l)
p(l)

Solution (Python):
def insertionSort(At, Nt):
	for i in range(Nt):
		v = At[i]
		j = i - 1
		while j >= 0 and At[j] > v:
			A[j + 1] = A[j]
			j = j - 1
		A[j + 1] = v
		print(" ".join(map(str,At)))
	return At

if __name__ == '__main__':
	N = int(input())
	A = list(map(int, input().split()))
	A = insertionSort(A, N)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

for k in range(N - 1):
    print(A[k], end = ' ')
print(A[N - 1])

for i in range(1, 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
    for k in range(N - 1):
        print(A[k], end = ' ')
    print(A[N - 1])

Solution (Python):
N = int(input())
A =list(map(int,input().split()))
def insertionSort(A, N):
    print(" ".join(map(str,A)))
    for i in range(1,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(" ".join(map(str,A)))


insertionSort(A,N)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
print(*a)
for i in range(1,n):
    num=a[i]
    j=i-1
    while j>=0 and a[j]>num:
        a[j+1]=a[j]
        j-=1
    a[j+1]=num
    print(*a)

Solution (Python):
def insertion_sort(N,input_list):
    for i in range(1,N):
        for j in range(N):
            if j != N - 1:
                print(input_list[j],end=" ")
            else:
                print(input_list[j])
        v = input_list[i]
        j = i - 1
        while j>=0 and input_list[j] > v:
            input_list[j+1] = input_list[j]
            j -= 1
            input_list[j+1] = v
    return input_list

def main():
    N = int(input())
    input_list = [int(i) for i in input().split()]
    input_list = insertion_sort(N,input_list)
    for i in range(N):
        if i != N - 1:
            print(input_list[i],end=" ")
        else:
            print(input_list[i])


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
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)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
print(" ".join(map(str,A)))

for i in range(1,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(" ".join(map(str,A)))

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
print(" ".join([str(a) for a in As]))

for i in range(1,N):
    tmp = As[i]
    j = i - 1
    
    
    while j >= 0 and As[j] > tmp:
        As[j+1] = As[j]
        j -= 1 
    As[j+1] = tmp
    print(" ".join([str(a) for a in As]))

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
print(" ".join(list(map(str, a))))


for i in range(1,len(a)):
    
    
    tmp=a[i]
    
    
    ins=0
    
    
    for j in range(i-1,-1,-1):
        
        
        if tmp < a[j]:
            
            
            a[j+1]=a[j]
        else :
            
            
            ins=j+1
            break
    
    
    a[ins]=tmp
    
    
    print(" ".join(list(map(str, a))))

Solution (Python):
n = int(input())
li = list(map(int, input().split()))

for i in range(n):
    v = li[i]
    j = i - 1
    while j >= 0 and li[j] > v:
        li[j+1] = li[j]
        j -= 1
    li[j+1] = v
    print(str(li).replace(',', '')[1:-1])

Solution (Python):
def insertionSort(n,a):
    for i in range(1,n):
        x = a[i]
        j = i
        print(*a)
        while j>0 and x < a[j-1]:
            a[j] = a[j-1]
            j -= 1
            a[j] = x

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    insertionSort(n,a)
    print(*a)

Solution (Python):
N = int(input())
A_INPUT = list(map(int, input().split()))

A = A_INPUT[:]

import bisect
for i in range(N):
    sorted_list = A[:i]
    v = A[i]
    unsorted_list = A[i+1:]
    bisect.insort(sorted_list, v)
    
    
        
    A = sorted_list + unsorted_list
    print(' '.join(map(str,A)))

Solution (Python):
n = int(input())
arr = list(map(int, input().split()))

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


insertionSort(arr, n)

Solution (Python):
def insertion_sort(A, n):
    for i in range(n):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1], A[j] = A[j], A[j+1]
            j-=1
        A[j+1] = v
        print(*A)
    
n = int(input())
A = list(map(int, input().split()))
insertion_sort(A, n)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
print(' '.join(map(str,a)))
for i in range(n-1):
    cur = sorted(a[:i+2])
    if i != n-2:
        print(' '.join(map(str,cur))+' '+' '.join(map(str,a[i+2:])))
    else:
        print(' '.join(map(str,cur)))

Solution (Python):
n = int(input())
a_list = list(map(int, input().split()))

print(' '.join(map(str, a_list)))
for i in range(1, n):
    key = a_list[i]
    j = i - 1
    while j >= 0 and a_list[j] > key:
        a_list[j + 1] = a_list[j]
        j = j - 1
    a_list[j + 1] = key
    print(' '.join(map(str, a_list)))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
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)

Solution (Python):
def insertionSort(A, N):
    for i in range(len(A)):
        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(' '.join([str(s) for s in A]))

input_line = input()
N = int(input_line)
input_line = input()
A = [int(s) for s in input_line.split(' ') if s]
insertionSort(A, N)

Solution (Python):
n=input()
N=int(n)
L=input().split()

A=[int(L[i]) for i in range(N)]







for i in range(N):
    v=A[i]
    j=i-1
    while j>=0 and A[j]>v:
        A[j+1]=A[j]
        j=j-1
    A[j+1]=v

    for k in range(N):
        if k<N-1:
            print(A[k],end=" ")
        else:
            print(A[k])

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

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(" ".join(map(str, A)))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))


def show(arr):
    for k in range(len(arr)):
        if k != len(arr) - 1:
            print(arr[k], end=' ')
        else:
            print(arr[k])



for i in range(len(A)):
    v = A[i]
    j = i - 1

    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j = j - 1

    A[j+1] = v

    show(A)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
print(" ".join(map(str,a)))
for i in range(1,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(" ".join(map(str,a)))

Solution (Python):
def insertionsort(A, N):
    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(" ".join(map(str,A)))
    return A

N = int(input())
A = list(map(int, input().split()))
A = insertionsort(A, N)

Solution (Python):
def show(lists):
    for i in range(len(lists)):
        if i != len(lists) - 1:
            print(lists[i], end=' ')
        else: print(lists[i])

length = int(input())
List = list(map(int, input().split()))

for i in range(length):
    term = List[i]
    j = i - 1
    while j >= 0 and List[j] > term: 
        List[j+1] = List[j]
        List[j] = term
        j = j - 1
    show(List)

Solution (Python):
n=int(input())
a=list(map(lambda x:int(x),list(input().split())))
for i in range(1,n):
    for k in range(n-1):
        print(a[k],end=" ")
    print(a[n-1])
    v=a[i]
    j=i-1
    while j>=0 and a[j]>v:
        a[j+1]=a[j]
        j=j-1
    a[j+1]=v

for k in range(n-1):
        print(a[k],end=" ")
print(a[n-1])

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    if i==n-1:
        print(a[i])
    else:
        print(a[i],end=' ')
for i in range(1,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
    for i in range(n):
        if i==n-1:
            print(a[i])
        else:
            print(a[i],end=' ')

Solution (Python):
def insertionSort(A, N):
    for i in range(1, N):
        print(*A, sep=" ")
        
        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, sep=" ")

    return A



N = int(input())

list_num = list(map(int, input().split()))

insertionSort(list_num, N)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
print(" ".join(list(map(str,A))))
for i in range(1,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(" ".join(list(map(str,A))))

Solution (Python):
def insertionSort(N):
    print(' '.join(map(str, A)))
    for i in range(1, 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(' '.join(map(str, A)))


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    insertionSort(N)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
print(' '.join([str(a) for a in A]))
for i in range(1, 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(' '.join([str(a) for a in A]))

Solution (Python):
def pr(sequence):
    string = ''
    for i in sequence[:-1]:
        string += str(i) + ' '
    string += str(sequence[-1])
    print(string)


n = int(input())
a = list(map(int, input().split()))

for i in range(1,n):
    pr(a)
    key = a[i]
    j = i -1
    while (j >=0) and (a[j] > key):
        a[j+1] = a[j]
        j = j-1
    a[j+1] = key
pr(a)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

print(*A)
for i in range(1, N):
  while A[i] < A[i-1] and i-1 >= 0:
    temp = A[i-1]
    A[i-1] = A[i] 
    A[i] = temp
    i -= 1
 
  print(*A)

Solution (Python):
def print_array(data):
	for i in range(len(data)):
		if i != len(data)-1:
			print("%d" % data[i],end=" ")
		else:
			print("%d" % data[i])

if __name__ == '__main__':
	num = int(input())
	a = [int(i) for i in input().split()]
	for i in range(1,num):
		print_array(a)
		key = a[i]
		j = i - 1
		while j >= 0 and a[j] > key:
			a[j+1] = a[j]
			j -= 1
		a[j+1] = key
	print_array(a)

Solution (Python):

n = int(input())
a = [int(i) for i in input().split()]
for i in range(1,n):
  print(" ".join([str(t) for t in a]))
  key = a[i]
  j = i - 1
  while j >= 0 and a[j] > key:
    a[j+1] = a[j]
    j -= 1
  a[j+1] = key
print(" ".join([str(t) for t in a]))

Solution (Python):
N = int(input())
a = list(map(int, input().strip().split()))

for j in range (1,N):
    for i in range(0, N-1):
        print(a[i], end=" ")
    print(a[N-1])
    temp = a[j]
    for k in range(0,j):
        if(temp<a[k]):
          a.pop(j)
          a.insert(k,temp)
          break
for l in range(0, N-1):
  print(a[l], end=" ")
print(a[N-1])

Solution (Python):
def lP(l: list) -> None:
    for i in range(len(l)-1):
        print(l[i], end = ' ')
    print(l[len(l)-1])

N = int(input())
l = list(map(int, input().split()))
for i in range(1, N):
    lP(l)
    v = l[i]
    for j in range(i-1, -1, -1):
        if v >= l[j]:
            break
        l[j+1] = l[j]
        l[j] = v
lP(l)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

def insertationSort(A, N):
    for i in range(1, N):
        print(" ".join(map(str, A)))
        
        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(" ".join(map(str, A)))
insertationSort(A, N)

Solution (Python):
num = int(input())
A = list(map(int, input().split()))
A_str = [str(a) for a in A]
print(' '.join(A_str))
for i in range(1,len(A)):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j-= 1
    A[j+1] = v
    A_str = [str(a) for a in A]
    print(' '.join(A_str))

Solution (Python):
def insertionSort (A, N):
    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
        printArray(A)

def printArray(A):
    for i,x in enumerate(A):
        if i != 0:
            print(" ", end="")
        print(x, end="")
    print("")

n = int(input())
a = list(int(x) for x in input().split())

insertionSort(a,n)

Solution (Python):
N = int(input())
list = list(map(str, input().split()))
print(' '.join(list))

for i in range(1, N):
  v = list[i]
  j = i - 1
  while j >= 0 and int(list[j]) > int(v):
    list[j+1] = list[j]
    j += -1
  list[j+1] = v
  print(' '.join(list))

Solution (Python):
a = int(input())
n = list(map(int, input().split()))

print(*n)

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
for i in range(1, N):
    for k in range(N):
        if k != N - 1:
            print(A[k], end=" ")
        else:
            print(A[N-1], 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
    print()
for k in range(N):
    if k != N - 1:
        print(A[k], end=" ")
    else:
        print(A[N-1])