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):
N = int(input())
A = [int(x) for x in input().split()]

print(" ".join(str(x) for x in A))


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
    print(" ".join(str(x) for x in A))

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

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

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

for i in range(0, n-1):
    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(map(str, a)))

Solution (Python):
n = int(input())
given_array = [int(x) for x in input().split()]

for i in range(1,n):
    print(" ".join([str(x) for x in given_array]))
    key = given_array[i]
    j = i - 1
    while j >= 0 and given_array[j] >= key:
        temp = given_array[j]
        given_array[j] = given_array[j+1]
        given_array[j+1] = temp
        j -= 1

    given_array[j+1] = key

print(" ".join([str(x) for x in given_array]))

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

def insertionSort(n, 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 = j - 1
		A[j+1] = key
		show(A)
		
n = int(input())
nums = list(map(int, input().split()))
show(nums)
insertionSort(n, nums)

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

def show(nums):
    for i in range(len(nums)):
        if i != len(nums)-1:
            print(nums[i],end=' ')
        else:
            print(nums[i])
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):
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):
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):
N = int(input())

lst = [ int(i) for i in input().split() ]

lstr = [ str(c) for c in lst ]
print(" ".join(lstr))

for i in range(1, N):
  v = lst[i]
  j = i - 1
  while 0 <= j and v < lst[j]:
    lst[j + 1] = lst[j]
    j -= 1
  
  lst[j + 1] = v

  lstr = [ str(c) for c in lst]
  print(" ".join(lstr))

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 = input().strip().split()
A = [int(i) for i in A]
for i in range(N):
    if i == N-1:
        print(A[i])
    else:
        print(A[i],end=' ')


for i in range(N-1):
    j = i
    while True:
        if j == -1:
            break
        if A[j]>A[j+1]:
            v = A[j]
            A[j] = A[j+1]
            A[j+1] = v
        j += -1
        
    for x in range(N):
        if x == N-1:
            print(A[x])
        else:
            print(A[x],end=' ')

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):
import sys






"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        
        
        
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    
    r, e, p = range, enumerate, print
    ip = IP()
    id = Idea()
    mod = 10 ** 9 + 7

    """この下から書いてね"""
    n = ip.I()
    a = ip.IL()
    p(*a)
    for i in r(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
        p(*a)


main()

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):
n = int(input())
nums = list(map(int,input().split()))
print(" ".join(map(str,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
    print(" ".join(map(str,nums)))

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):
    for j in range(i):
        if a[i] > a[i-j-1]:
            temp = a.pop(i)
            a.insert(i-j,temp)
            break
        elif j == i - 1:
            temp = a.pop(i)
            a.insert(0,temp)
    print(" ".join(map(str,a)))

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

Solution (Python):
def show(nums):
    print(" ".join(list(map(str, nums))))


def insertion_sort(nums):
    show(nums)
    for i in range(1, len(nums)):
        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)


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

Solution (Python):
def pr(A):
    N = len(A);
    for i in range(N):
        if i :
            print (" ", end = "");
        print (A[i], end = "")
    print ("")

def insertionSort(A):
    pr(A)
    N = len(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 = j - 1
        A[j+1] = v
        pr(A)

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

insertionSort(A)

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

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

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

insertionSort(Line_A, N)

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

def insec_sort(A, N):

    for i in range(1, N):
        print(*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(*A)


insec_sort(A,N)

Solution (Python):
N = int(input())
A = input().split()
print(' '.join(A))
A = [int(s) for s in A]
while A != sorted(A):
    for i in range(1, N):
        tmp = A[i]
        if A[i-1] > tmp:
            j = i
            while j >0 and A[j-1] > tmp:
                A[j] = A[j-1]
                j -= 1
            A[j] = tmp
        result = map(str, A)
        print(' '.join(result))

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):
import bisect
n=int(input())
a=list(map(int,input().split()))
print(' '.join(map(str,a)))
for i in range(1,n):
    a_n=a.pop(i)
    insert_index = bisect.bisect_left(a[:i],a_n)
    a.insert(insert_index,a_n)
    print(' '.join(map(str,a)))

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


n = int(input())
a = [int(i) for i in input().split()]


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

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

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

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

Solution (Python):
def readInt():
  return int(input())


def readInts():
  return [int(i) for i in input().split()]


N = readInt()
AS = readInts()

print(' '.join([str(i) for i in AS]))
for i, a in enumerate(AS[1:]):
    while i >= 0 and AS[i] > a:
        AS[i + 1] = AS[i]
        i -= 1
    AS[i + 1] = a
    print(' '.join([str(i) for i in AS]))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = map(str, a)
print(' '.join(b))
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
    b = map(str, a)
    print(' '.join(b))

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



count = int(input())
tmp = input().split(" ")
nums = []
for i in tmp:
    nums.append(int(i))
solution(count,nums)

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):
def insertion_sort(A):
    global N 
    for i in range(1, N):
        key = A[i]
        j = i - 1
        while A[j] > key and j >= 0:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = key
        print(' '.join(list(map(str, A))))
    return 
N = int(input())
A = list(map(int, input().split()))
print(' '.join(list(map(str, A))))
insertion_sort(A)

Solution (Python):
n,*a=map(int,open(0).read().split())
for i in range(1,n):
    print(*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(*a)

Solution (Python):
n = int(input())
*v, = map(int, input().split())
v = v[:n]

for i in range(n):
    k = v[i]
    j = i-1
    while j >= 0 and v[j] > k:
        v[j+1] = v[j]
        j -= 1
    v[j+1] = k
    print(" ".join([str(_v) for _v in v]))

Solution (Python):
import sys

n = int(input())
nums = [int(num) for num in input().split(" ")]

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

        result = ""
        for k in range(0, n - 1):
            result += str(nums[k])
            result += " "
        result += str(nums[n - 1])
        print(result)

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

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

insertionSort(N,A)

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


for i in range(int(Num_factor)):
    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(" ".join(map(str,N)))

Solution (Python):
length = int(input())
raw_list = input().split()
for i in range(length):
	raw_list[i] = int(raw_list[i])
for i in range(length):
	key = raw_list[i]
	j = i - 1
	while j >= 0 and raw_list[j] > key:
		raw_list[j+1] = raw_list[j]
		j -= 1
	raw_list[j+1] = key
	for k in range(length):
		if k-length+1:
			print(raw_list[k], end=' ')
		else:
			print(raw_list[k])

Solution (Python):
def Show():
    print(' '.join([str(aa) for aa in a]))

n = int(input())
a = list(map(int, input().split()))
Show()
for i in range(1, n):
    target = a[i]
    j = i-1 
    while j >= 0 and a[j] > target:
        a[j+1] = a[j] 
        j -= 1
    a[j+1] = target
    Show()

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(list(map(str, a))))
n = int(input())
a = list(map(int, input().split()))
print(' '.join(list(map(str, a))))
insertionSort(a, n)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
for h in range(len(A)):
    if h == len(A)-1:
        print(A[h])
    else:
        print(A[h], "", end="")
def insertionSort(A, N):
    for i in range(1, N):
        temp = A[i]
        j = i -1
        while j >= 0 and temp < A[j]:
            A[j+1] = A[j]
            j -= 1
        A[j + 1] = temp
        for k in range(len(A)):
            if k == len(A)-1:
                print(A[k])
            else:
                print(A[k], "", end="")

insertionSort(A, N)

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

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

Solution (Python):
n = int(input())
r = list(map(int,input().split()))
for i in range(n):
    value = r[i]
    while i >= 1 and r[i-1] > value:
        r[i] = r[i-1]
        i -= 1
    r[i] = value
    print(*r)

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

Solution (Python):
def pres(data, N):
    for i in range(N):
        if i < N-1:
            print('%d '%data[i], end='')
        else:
            print(data[i])
        
def ins_sort(data, N):
    for i in range(1, N):
        flag = data[i]
        j = i-1
        while j>=0 and data[j]>flag:
            data[j+1] = data[j]
            j-=1
        data[j+1] = flag
        pres(data, N)
    
    
N = int(input())
data  = list(map(int, input().split()))

pres(data, N)
ins_sort(data, N)

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 = j - 1
        A[j + 1] = v
        print(' '.join(map(lambda x: str(x), A)))
    return A

N = input()

while True:
    try:
        line = raw_input()
        print(line)
        num_list = map(lambda x : int(x), line.strip().split())
        insertionSort(num_list, N)
    except EOFError:
        break

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

Solution (Python):


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

def insertionSort(a, n):
    printA(ai, 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
        printA(ai, n)

num = int(input().rstrip())
ai = list(map(int,input().rstrip().split()))
insertionSort(ai, num)

Solution (Python):
def trace(A: list):
    print(*A)

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

    return A


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

trace(A)
insertionSort(A, N)

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())
A = list(map(int,input().split()))
show(A)
for i in range(1,N):
    v = A[i]
    while i - 1 >= 0 and A[i-1] > v:
        A[i] = A[i-1]
        i -= 1
    A[i] = v
    show(A)

Solution (Python):


def insertion_sort(array):
    putsarray(array)
    N = len(array)
    for i in range(1, N):
        j = i - 1
        num = array[i]
        while j >= 0 and array[j] > num:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = num
        putsarray(array)

def putsarray(array):
    for i in range(len(array) - 1):
        print(array[i], end=" ")
    print(array[-1])


N = int(input())
array = input().split()
array = [int(n) for n in array]
insertion_sort(array)

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

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

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=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+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()))
for i in range(n):
  for j in range(1, n):
    if i-j >= 0 and a[i-j] > a[i-j+1]:
      a[i-j], a[i-j+1] = a[i-j+1], a[i-j]
    else:
      break
  print(" ".join([str(i) for i in a]))

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

ins(N, A)

Solution (Python):
def insertionSort(A, N):
    '''list of int, int(=len(A)) -> list of int
    return sorted list(insertion sort)
    '''
    l = N
    outA = A.copy()
    for i in range(l):
        val = outA[i]
        j = i - 1
        while j >= 0 and outA[j] > val:
            outA[j + 1] = outA[j]
            j -= 1
        outA[j + 1] = val
        printlist(outA)
    return outA
def printlist(L):
    '''
    print list with space
    '''
    for item in L[:-1]:
        print(item, end = ' ')
    print(L[-1])

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

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

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

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

Solution (Python):
def insertion_sort(A):
    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
        print(' '.join([str(x) for x in A]))


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

print(' '.join([str(x) for x in A]))

insertion_sort(A)

Solution (Python):
def insert(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(*A)
        

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

Solution (Python):
input();a=list(map(int,input().split()));print(*a)
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;print(*a)

Solution (Python):


def printArrLine( arr ):
    print(' '.join(list(map(str,arr))))
    
def inputArrLine():
    return [int(i) for i in input().split()]
    
def insert( arr ):
    n = len(arr)
    printArrLine(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 = j-1
        arr[j+1] = v
        printArrLine(arr)

n = int(input())

ar = inputArrLine()

insert(ar)

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

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

"""
Created on Sat Jan 26 21:11:25 2019

@author: Yamazaki Kenichi
"""

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())
I = list(map(int, input().split()))

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

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

Solution (Python):
n = int(input())
a = input().split()
print(" ".join(a))
a1 = [a[0]]
a2 = a[1:]
for _ in range(n - 1):
    for j, k in enumerate(a1):
        if int(a2[0]) < int(k):
            if j == 0:
                a1.insert(0, a2[0])
            else:
                a1.insert(j, a2[0])
            break
    else:
        a1.append(a2[0])
    del a2[0]
    print(" ".join(a1 + a2))

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):
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 show(list1):
  for i in range(len(list1)):
    if i<len(list1)-1:
      print(list1[i],end=' ')
    else:
      print(list1[i])  

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

show(list1)

for i in range(1,n):
  key = list1[i]
  j = i-1
  while j>=0 and key<list1[j]:
    list1[j+1]=list1[j]
    j-=1
  list1[j+1] = key
  
  for i in range(n):
    if i<n-1:
      print(list1[i],end=' ')
    else:
      print(list1[i])

Solution (Python):
def insertion_sort(a):
    for i in range(1,len(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
        print(*a,sep=' ')
    return a


if __name__ == '__main__':
    n = input()
    a = list(map(int,input().split()))
    print(*a,sep=' ')
    insertion_sort(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 v < A[j]:
        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 insertionSort(A, N):
    for k in range(len(A)):
        if k != len(A) - 1:
            print(A[k], end=" ")
        else:
            print(A[k])
    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(len(A)):
            if k != len(A) - 1:
                print(A[k], end=" ")
            else:
                print(A[k])



insertionSort(A, N)

Solution (Python):
def list_print(A):
    ret = str(A[0])
    for i in range(1, len(A)):
        ret += " " + str(A[i])

    print(ret)
    return True


n = int(input())
A = list(map(int, input().split()))
list_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

    list_print(A)

Solution (Python):
import sys


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


n = int(sys.stdin.readline())
a = [int(v) for v in sys.stdin.readline().strip().split()]
insertion_sort(a)