In Insertion Sort Part 1, you inserted one element into an array at its correct sorted position. Using the same approach repeatedly, can you sort an entire array?

Guideline: You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that in the first step, when you consider an array with just the first element, it is already sorted since there's nothing to compare it to.

In this challenge, print the array after each iteration of the insertion sort, i.e., whenever the next element has been inserted at its correct position.  Since the array composed of just the first element is already sorted, begin printing after placing the second element.

Example. 

$n=7$ 

$arr=[3,4,7,5,6,2,1]$   

Working from left to right, we get the following output:

3 4 7 5 6 2 1
3 4 7 5 6 2 1
3 4 5 7 6 2 1
3 4 5 6 7 2 1
2 3 4 5 6 7 1
1 2 3 4 5 6 7

Function Description

Complete the insertionSort2 function in the editor below.  

insertionSort2 has the following parameter(s):  

int n: the length of $\textbf{arr}$  
int arr[n]: an array of integers  

Prints  

At each iteration, print the array as space-separated integers on its own line.  

Input Format

The first line contains an integer, $n$, the size of $\textbf{arr}$. 

 The next line contains $n$ space-separated integers $arr\left[i\right]$.  

Constraints

$1\leq n\leq1000$ 

$-10000\leq arr[i]\leq10000,0\leq i\lt n$ 

Output Format

Print the entire array on a new line at every iteration.

Sample Input
STDIN           Function
-----           --------
6               n = 6
1 4 3 5 6 2     arr = [1, 4, 3, 5, 6, 2]

Sample Output
1 4 3 5 6 2 
1 3 4 5 6 2 
1 3 4 5 6 2 
1 3 4 5 6 2 
1 2 3 4 5 6 

Explanation

Skip testing $\mbox{1}$ against itself at position $\mbox{0}$.  It is sorted. 

Test position $\mbox{1}$ against position $\mbox{0}$: $4>1$, no more to check, no change. 

Print $\textbf{arr}$ 

Test position $2$ against positions $\mbox{1}$ and $\mbox{0}$: 

$3<4$, new position may be $\mbox{1}$.  Keep checking.    
$3>1$, so insert $3$ at position $\mbox{1}$ and move others to the right.   

Print $\textbf{arr}$ 

Test position $3$ against positions $2,1,0$ (as necessary): no change. 

Print $\textbf{arr}$ 

Test position $\begin{array}{c}4\end{array}$ against positions $3,2,1,0$: no change. 

Print $\textbf{arr}$ 

Test position $5$ against positions $4,3,2,1,0$, insert $2$ at position $\mbox{1}$ and move others to the right. 

Print $\textbf{arr}$

Difficulty: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
size = int(input())
array = input().split(' ')
arr = ['None'] * size
for i in range(size):
	arr[i] = int(array[i])
i = 1
while i < size:
	tmp = arr[i]
	j = i - 1
	while arr[j] > tmp and j > -1:
		arr[j + 1] = arr[j]
		j = j - 1
	arr[j + 1] = tmp
	for k in range(size):
		print(arr[k], end=' ')
	print()
	i = i + 1


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

def list_print(lst):
	print(' '.join(map(str, lst)))

def insert(lst, i):
	pos = i - 1
	for pos in range(i - 1, -1, -1):
		if lst[pos] > lst[pos + 1]:
			(lst[pos], lst[pos + 1]) = (lst[pos + 1], lst[pos])
for stop in range(1, n):
	insert(line, stop)
	list_print(line)


s = int(input())
input_ar = input().split()
ar = [int(x) for x in input_ar]
for i in range(1, s):
	j = i - 1
	if ar[i] >= ar[j]:
		print(' '.join([str(x) for x in ar]))
		continue
	v = ar[i]
	while v < ar[j] and j >= 0:
		ar[j + 1] = ar[j]
		j -= 1
	ar[j + 1] = v
	print(' '.join([str(x) for x in ar]))


n = int(input())
d = [int(x) for x in input().split()]
i = 1
while i < n:
	k = i
	while k > 0 and d[k] < d[k - 1]:
		(d[k], d[k - 1]) = (d[k - 1], d[k])
		k -= 1
	i += 1
	s = str(d)[1:-1].replace(',', '')
	print(s)


def insertionSort(x):
	p = len(x) - 1
	for k in range(p):
		y = x[-1]
		if y < x[-2]:
			for i in range(p, 0, -1):
				if x[i - 1] >= y:
					x[i] = x[i - 1]
				else:
					x[i] = y
					break
			if x[0] >= x[1]:
				x[0] = y
		else:
			break
	return x

def insertionSort2(x):
	l = len(x)
	m = [x[0]]
	s = []
	for i in range(1, l):
		m.append(x[i])
		if x[i] < x[i - 1]:
			insertionSort(m)
		x = m + x[i + 1:]
		print(' '.join((str(j) for j in x)))
	return x
m = input()
ar = [int(i) for i in input().strip().split()]
insertionSort2(ar)


import sys
count = None
a_list = None
for line in sys.stdin:
	if count is None:
		count = int(line.strip())
		continue
	a_list = [int(i) for i in line.strip().split(' ')]
for i in range(1, count):
	V = a_list[i]
	for j in range(i):
		if V < a_list[i - j - 1]:
			tmp = a_list[i - j - 1]
			a_list[i - j - 1] = V
			a_list[i - j] = tmp
	print(' '.join([str(x) for x in a_list]))


import sys

def insertionSort(ar):
	output = ''
	i = 1
	done = False
	ar[0] = int(ar[0])
	while i < len(ar):
		done = False
		toInsert = int(ar.pop(i))
		j = 0
		while j < i and (not done):
			if ar[j] > toInsert:
				ar.insert(j, toInsert)
				done = True
			j += 1
		if not done and j != len(ar):
			ar.insert(j, toInsert)
		elif not done:
			ar.append(toInsert)
		i += 1
		for val in ar:
			output += str(int(val)) + ' '
		output += '\n'
	return output.strip()
length = int(sys.stdin.readline())
array = sys.stdin.readline().split(' ')
print(insertionSort(array[0:length]))


def insert(ar):
	u = ar.pop()
	for i in range(len(ar)):
		if ar[i] >= u:
			ar.insert(i, u)
			return ar
	ar.append(u)
	return ar

def insertionSort(ar):
	for i in range(2, len(ar) + 1):
		ar[0:i] = insert(ar[0:i])
		print(' '.join([str(i) for i in ar]))
m = int(input())
ar = [int(i) for i in input().strip().split()]
if m == 1:
	print(' '.join([str(i) for i in ar]))
elif m == len(ar):
	insertionSort(ar)


def insertionSort(m, ar):
	if m < 2:
		print(' '.join([str(x) for x in ar]))
	for index in range(1, m):
		while ar[index] < ar[index - 1]:
			(ar[index], ar[index - 1]) = (ar[index - 1], ar[index])
			if index > 1:
				index -= 1
		print(' '.join([str(x) for x in ar]))
m = int(input())
ar = [int(i) for i in input().strip().split()]
insertionSort(m, ar)


def insertionSort2(ar):
	s = len(ar) - 2
	check = int(ar[-1])
	for x in range(s, -1, -1):
		if int(ar[x]) <= check:
			ar[x + 1] = str(check)
			break
		else:
			ar[x + 1] = ar[x]
			if x == 0:
				ar[0] = str(check)
	return ar
s = input()
ar = input()
ar = ar.split()
for x in range(2, len(ar) + 1):
	ar_check = insertionSort2(ar[:x])
	ar_rest = ar[x:]
	ar = ar_check + ar_rest
	print(' '.join(ar))


import sys

def display(array):
	[print(x, end=' ') for x in array]
	print()
N = int(sys.stdin.readline())
array = [int(X) for X in sys.stdin.readline().split()]
for i in range(1, N):
	num = array[i]
	for j in range(i - 1, -1, -1):
		if array[j] > num and j != 0:
			array[j + 1] = array[j]
		elif array[j] > num and j == 0:
			array[j + 1] = array[j]
			array[j] = num
		else:
			array[j + 1] = num
			break
	display(array)


x = int(input())
a = input().split()
if x == 1:
	print(a[0])
j = 1
while j < x:
	i = j
	v = int(a[i])
	while i > 0:
		t1 = int(a[i - 1])
		if t1 > v:
			a[i] = t1
			a[i - 1] = v
		i -= 1
	for num in a:
		print(num, end=' ')
	print()
	j += 1


def insertionSort(ar):
	x = len(ar)
	v = ar[x - 1]
	j = x - 2
	finarr = []
	while ar[j] > v:
		j = j - 1
	for k in range(0, j + 1):
		finarr.append(ar[k])
		print(ar[k], end=' ')
	finarr.append(v)
	print(v, end=' ')
	for k in range(j + 2, x):
		finarr.append(ar[k - 1])
		print(ar[k - 1], end=' ')
	return finarr
n = int(input(''))
elem = input('')
numbers = elem.split()
arr = []
newarr = []
for i in range(0, n):
	arr.append(int(numbers[i]))
newarr.append(arr[0])
for i in range(1, n):
	newarr.append(arr[i])
	newarr = insertionSort(newarr)
	for j in range(i + 1, n):
		print(arr[j], end=' ')
	print('')


l = int(input())
ar = input().split()
for size in range(l):
	ar[size] = int(ar[size])

def shift(plist, index):
	temp = plist[index]
	if plist[index - 1] > plist[index]:
		plist[index] = plist[index - 1]
		plist[index - 1] = temp
		if index - 2 == -1:
			pass
		else:
			shift(plist, index - 1)
	return plist
for listing in range(1, l):
	string = ''
	ar = shift(ar, listing)
	for size2 in range(l):
		string = string + str(ar[size2]) + ' '
	print(string)


def ordena(lista):
	g_num = lista[-1]
	for x in range(len(lista) - 2, -1, -1):
		if lista[x] >= g_num:
			lista[x + 1] = lista[x]
			if x == 0:
				lista[0] = g_num
		else:
			lista[x + 1] = g_num
			break
	return lista
r = int(input())
g_numbers = [int(v) for v in input().split(' ')]
for x in range(0, len(g_numbers)):
	g_numbers[0:x + 1] = ordena(g_numbers[0:x + 1])
	if x > 0:
		print('%s' % ' '.join(map(str, g_numbers)))


def sort(li, i):
	j = i - 1
	while j >= 0:
		if li[j] <= li[i]:
			break
		help = li[i]
		li[i] = li[j]
		li[j] = help
		i -= 1
		j -= 1
	print(' '.join(map(str, li)))
n = int(input())
array = [int(x) for x in input().split()]
for i in range(1, n):
	sort(array, i)


def insert(ar, index):
	while index > 0:
		if ar[index - 1] > ar[index]:
			tmp = ar[index]
			ar[index] = ar[index - 1]
			ar[index - 1] = tmp
			index = index - 1
		else:
			return ar
	return ar

def insertionSort(ar):
	for i in range(len(ar) - 1):
		ar = insert(ar, i + 1)
		print(*ar)
num = [int(i) for i in input().strip().split()]
ar = [int(j) for j in input().strip().split()]
insertionSort(ar)


import sys

def print_ar(a):
	for i in a:
		print(i, end=' ')
	print('')

def insert_key(n, ar):
	key = ar[n - 1]
	k = n - 1
	for i in range(n - 2, -1, -1):
		if key < ar[i]:
			ar[i + 1] = ar[i]
			k = k - 1
		else:
			break
	ar[k] = key
	print_ar(ar)
n = int(sys.stdin.readline())
raw = sys.stdin.readline().split()
ar = []
for i in raw:
	ar.append(int(i))
if n < 2:
	print_ar(ar)
else:
	for i in range(2, n + 1):
		insert_key(i, ar)


def insertionSort1(arr):
	length = len(arr)
	v = arr[length - 1]
	if length == 2:
		if arr[1] < arr[0]:
			arr = [arr[1], arr[0]]
		return arr
	for i in range(length - 2, -1, -1):
		if arr[i] > v:
			arr[i + 1] = arr[i]
		else:
			arr[i + 1] = v
			break
	if arr[0] > v:
		arr[0] = v
	return arr

def insertionSort(arr):
	length = len(arr)
	for i in range(1, length):
		if arr[i] < arr[i - 1]:
			arr[:i + 1] = insertionSort1(arr[:i + 1])
		temp = arr
		s = ''
		for j in temp:
			s = s + repr(j) + ' '
		print(s.strip())
length = int(input())
temp = input().strip().split()
arr = []
for i in range(0, len(temp)):
	arr.append(int(temp[i]))
insertionSort(arr)


import sys

def insert(ar):
	e = int(len(ar)) - 1
	newNum = ar[e]
	done = False
	while done == False:
		if ar[e - 1] > newNum:
			ar[e] = ar[e - 1]
			e -= 1
			done = e == 0
		else:
			done = True
	ar[e] = newNum
	return ar

def insertionSort(ar):
	if len(ar) > 1:
		for i in range(1, len(ar)):
			if ar[i - 1] > ar[i]:
				ar[0:i + 1] = insert(ar[0:i + 1])
			buildString(ar)
	return ar

def buildString(ar):
	string = str(' ')
	for i in range(len(ar)):
		string += str(ar[i]) + ' '
	sys.stdout.write(string.strip() + '\n')
	return string

def raw_input():
	m = input()
	return m

def main():
	m = int(input())
	i = int(0)
	ar = list()
	ar = [int(i) for i in raw_input().strip().split()]
	insertionSort(ar)
	return 0
main()


def listprint(lst):
	print(' '.join(map(str, lst)))

def insertionSort(lst):
	for startIndex in range(1, len(lst)):
		startNum = lst[startIndex]
		currentIndex = startIndex
		while currentIndex > 0 and lst[currentIndex - 1] > startNum:
			currentIndex -= 1
		del lst[startIndex]
		lst.insert(currentIndex, startNum)
		listprint(lst)
import sys
lst = map(int, sys.stdin.readlines()[1].split())
insertionSort(list(lst))


import sys

def print_list(ar):
	print(' '.join(map(str, ar)))

def insertion_sort(ar):
	if len(ar) == 1:
		print_list(ar)
		return ar
	else:
		for j in range(1, len(ar)):
			for i in reversed(range(j)):
				if ar[i + 1] < ar[i]:
					(ar[i], ar[i + 1]) = (ar[i + 1], ar[i])
				else:
					break
			print_list(ar)
		return ar
s = int(sys.stdin.readline())
ar = list(map(int, sys.stdin.readline().split()))
insertion_sort(ar)


import sys

def insertionSort(startIdx, a, t):
	for idx in range(startIdx, 0, -1):
		if a[idx] < a[idx - 1]:
			(a[idx - 1], a[idx]) = (a[idx], a[idx - 1])
		elif a[idx] >= a[idx - 1]:
			break
	for x in a:
		sys.stdout.write('{} '.format(x))
	sys.stdout.write('\n')
t = int(input())
a = list(map(int, sys.stdin.readline().split()))
for i in range(1, t):
	insertionSort(i, a, t)


import sys
x = int(input())
number = input()
s = [int(s) for s in number.split()]
for i in range(1, len(s)):
	val = s[i]
	j = i - 1
	while j >= 0 and s[j] > val:
		s[j + 1] = s[j]
		j = j - 1
	s[j + 1] = val
	for i in range(0, x):
		print(s[i], end=' ')
	print()


s = input()
l = [int(i) for i in input().split()]
for i in range(1, len(l)):
	for j in range(0, i):
		if l[i] < l[j]:
			(l[j], l[i]) = (l[i], l[j])
	print(' '.join([str(i) for i in l]))


import sys

def print_out(ar):
	print(' '.join([str(x) for x in ar]))

def insert_in_place(ar):
	if not ar:
		return
	insert_val = ar[-1]
	for check_val in reversed(ar[:-1]):
		if check_val > insert_val:
			ar[ar.index(check_val) + 1] = check_val
		else:
			ar[ar.index(check_val) + 1] = insert_val
			break
	if insert_val < ar[0]:
		ar[0] = insert_val

def insertionSort(ar):
	in_order = []
	in_order.append(ar[0])
	unsorted = ar[1:]
	print_ar = ar[1:]
	for x in unsorted:
		print_ar.remove(x)
		in_order.append(x)
		insert_in_place(in_order)
		print_out(in_order + print_ar)
lines = sys.stdin.readlines()
size = int(lines[0])
if not size:
	exit(0)
if size == 1:
	print(lines[1])
	exit(0)
ar = [int(x) for x in lines[1].split(' ')]
insertionSort(ar)


import pdb

def display(ar):
	for i in ar:
		print(i, end=' ')
	print()

def insertionSort(ar):
	for i in range(1, len(ar)):
		if ar[i] > ar[i - 1]:
			display(ar)
			continue
		else:
			v = ar[i]
			index = i
			while ar[index - 1] > v:
				ar[index] = ar[index - 1]
				index -= 1
				if index == 0:
					break
			ar[index] = v
			display(ar)
n = int(input())
temp = input().split(' ')
ar = []
for i in temp:
	ar.append(int(i))
insertionSort(ar)


n = int(input())
ar = [int(x) for x in input().split(' ')]
for s in range(1, n):
	v = ar[s]
	i = s - 1
	while i >= 0 and ar[i] > v:
		ar[i + 1] = ar[i]
		i -= 1
	ar[i + 1] = v
	print(' '.join([str(x) for x in ar]))


import copy

def printArrayAsString(arToPrint):
	strInt = []
	for val in arToPrint:
		strInt.append(str(val))
	print(' '.join(strInt))

def basicInsertionSort(arIntegers):
	arIntProcess = copy.copy(arIntegers)
	for val in range(len(arIntegers)):
		if val == 0:
			continue
		if arIntegers[val] < arIntProcess[val - 1]:
			numIndexToInsert = 0
			for indexSeek in range(len(arIntProcess)):
				if arIntProcess[indexSeek] < arIntegers[val]:
					continue
				numIndexToInsert = indexSeek
				break
			arIntProcess.insert(numIndexToInsert, arIntegers[val])
			numIndexToRemove = 0
			for indexSeek in range(numIndexToInsert + 1, len(arIntProcess)):
				if arIntProcess[indexSeek] != arIntegers[val]:
					continue
				numIndexToRemove = indexSeek
				break
			arIntProcess.pop(numIndexToRemove)
		printArrayAsString(arIntProcess)
	return arIntProcess

def main():
	strNumLengthArray = input()
	stringIntRepresentation = input()
	arStringInt = stringIntRepresentation.split()
	numLengthArray = int(strNumLengthArray)
	arInt = []
	for str in arStringInt:
		arInt.append(int(str))
	if len(arInt) == numLengthArray:
		basicInsertionSort(arInt)
	else:
		print('Not valid input')
main()


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

def myInsert(myList, num):
	j = 0
	while num > myList[j]:
		j += 1
	myList.insert(j, num)
	return myList
for i in range(1, N):
	if not myList[i - 1] < myList[i]:
		temp = myList[i]
		del myList[i]
		myInsert(myList, temp)
	for x in myList:
		print(x, end=' ')
	print()


def start():
	s = int(input())
	text = input().split(' ')
	a = []
	for i in range(s):
		a.append(int(text[i]))
	return a

def printArray(a):
	n = len(a) - 1
	for i in range(n):
		print(a[i], ' ', sep='', end='')
	print(a[n])

def insertionSort(a):
	for i in range(1, len(a)):
		v = a[i]
		j = i - 1
		while j >= 0:
			if a[j] > v:
				a[j + 1] = a[j]
				a[j] = v
			j -= 1
		printArray(a)
insertionSort(start())


def printArr(arr):
	for i in range(len(arr)):
		print(arr[i], end=' ')
size = int(input())
arr = input().strip().split()
arr = [int(entry) for entry in arr]
for i in range(1, size):
	key = arr[i]
	j = i - 1
	while j >= 0 and arr[j] > key:
		arr[j + 1] = arr[j]
		j -= 1
	arr[j + 1] = key
	printArr(arr)
	print()


l = []
n = int(input())
l = input().split(' ')
for i in range(0, n):
	l[i] = int(l[i])

def P():
	for j in range(0, n):
		print('%d ' % l[j], end='')
	print()
for i in range(1, n):
	j = i - 1
	x = l[i]
	while (j >= 0) & (x < l[j]):
		l[j + 1] = l[j]
		j = j - 1
	l[j + 1] = x
	P()


n = input()
nums = list(map(int, input().split()))
for i in range(1, len(nums)):
	val = nums[i]
	while i > 0 and nums[i - 1] > val:
		nums[i] = nums[i - 1]
		i = i - 1
	nums[i] = val
	print(' '.join(map(str, nums)))


import sys

def insertionSort():
	arlen = int(sys.stdin.readline())
	temp_ar = sys.stdin.readline().split()
	ar = []
	for a in temp_ar:
		ar.append(int(a))
	i = 1
	switch = False
	while i < len(ar):
		j = i
		switch = False
		while ar[j] < ar[j - 1] and j > 0:
			(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
			switch = True
			j -= 1
		i += 1
		for num in ar:
			print(num, '', end='')
			if ar.index(num) == len(ar) - 1:
				print()
insertionSort()


def insertionSort(ar):
	for i in range(1, len(ar)):
		t = ar[i]
		j = i
		while j > 0 and ar[j - 1] > t:
			ar[j] = ar[j - 1]
			j -= 1
		ar[j] = t
		print(' '.join(map(str, ar)))
	return ''
m = input()
ar = [int(i) for i in input().strip().split()]
insertionSort(ar)


import fileinput

def arrayToPrint(loi):
	itr = 0
	retString = ''
	while itr < len(loi):
		if itr == 0:
			retString = str(loi[itr])
		else:
			retString += ' ' + str(loi[itr])
		itr = itr + 1
	print(retString)

def insert(intToInsert, whatToInsert, loi):
	while whatToInsert > 0:
		if loi[whatToInsert - 1] > loi[whatToInsert]:
			temp = loi[whatToInsert - 1]
			loi[whatToInsert - 1] = loi[whatToInsert]
			loi[whatToInsert] = temp
			whatToInsert = whatToInsert - 1
		else:
			break
	return loi

def insertionSort(loi, numInts):
	whatToInsert = 1
	while whatToInsert < numInts:
		loi = insert(loi[whatToInsert], whatToInsert, loi)
		arrayToPrint(loi)
		whatToInsert = whatToInsert + 1
itr = 0
numInts = 0
loi = []
for line in fileinput.input():
	if itr == 0:
		numInts = int(line)
	else:
		loi = line.split(' ')
	itr = itr + 1
itr = 0
while itr < numInts:
	loi[itr] = int(loi[itr])
	itr = itr + 1
insertionSort(loi, numInts)


def insertionSort(ar):
	l = len(ar)
	val = ar[l - 1]
	srt = False
	N = l - 1
	while not srt:
		if N == 0 or val > ar[N - 1]:
			ar[N] = val
			srt = True
		else:
			ar[N] = ar[N - 1]
		N = N - 1
	return ar
N = int(input())
ar = [int(x, 10) for x in input().split()]
for i in range(2, N + 1):
	ar = insertionSort(ar[:i]) + ar[i:]
	for x in ar:
		print(x, end=' ')
	print()


L = int(input(''))
arr = input('').split()
for j in range(2, L + 1):
	ar = arr[0:j]
	V = ar[-1]
	l = len(ar)
	for i in range(1, l):
		if int(V) < int(ar[l - i - 1]):
			ar[l - i] = ar[l - i - 1]
		else:
			ar[l - i] = V
			break
	else:
		ar[0] = V
	arr[0:j] = ar
	print(' '.join(arr))


def sortLastElement(s, ar, i):
	number = ar[i]
	while i > 0 and ar[i - 1] > number:
		ar[i] = ar[i - 1]
		i = i - 1
	ar[i] = number
	return ar

def insertionSort(ar):
	s = len(ar)
	for i in range(1, s):
		ar = sortLastElement(s, ar, i)
		print(' '.join(map(str, ar)))
s = int(input())
ar = list(map(int, input().split(' ')))
insertionSort(ar)


s = int(input())
numbers = input().split(' ')
checker = True
i = int(0)
w = int(0)
if s == 1:
	print(' '.join(numbers))
while i < s - 1 and checker == True:
	if int(numbers[i + 1]) < int(numbers[i]):
		temp = numbers[i]
		numbers[i] = numbers[i + 1]
		numbers[i + 1] = temp
		w = int(i)
		if w == 0:
			print(' '.join(numbers))
		while w > 0:
			if int(numbers[w]) < int(numbers[w - 1]):
				temp = numbers[w - 1]
				numbers[w - 1] = numbers[w]
				numbers[w] = temp
				w = w - 1
				if w == 0:
					print(' '.join(numbers))
			elif int(numbers[w]) > int(numbers[w - 1]):
				print(' '.join(numbers))
				w = 0
		i = i + 1
	elif int(numbers[i + 1]) > int(numbers[i]):
		print(' '.join(numbers))
		i = i + 1


s = int(input())
ar = input().split(' ')
i = 0
loop = s - 1
while loop > 0:
	if int(ar[i]) < int(ar[i + 1]):
		print(' '.join(ar))
		loop -= 1
		i += 1
	else:
		another = i
		while int(ar[another]) > int(ar[another + 1]):
			current = ar[another]
			nextOne = ar[another + 1]
			ar[another] = nextOne
			ar[another + 1] = current
			another -= 1
			if int(another) == -1:
				break
		print(' '.join(ar))
		i += 1
		loop -= 1


import sys
import bisect
size = int(sys.stdin.readline())
array = list(map(int, sys.stdin.readline().split()))
for i in range(1, len(array)):
	if array[i] < array[i - 1]:
		val = array[i]
		tmparray = array[:i] + array[i + 1:]
		index = bisect.bisect_right(tmparray, val, 0, i)
		tmparray.insert(index, val)
		array = tmparray
	print(' '.join(map(str, array)))


import sys

def printList(ar):
	a = ''
	for i in ar:
		a += str(i) + ' '
	print(a)

def insertionSort(n, ar):
	for i in range(1, n):
		V = ar.pop(i)
		for j in range(i):
			if ar[j] > V:
				ar.insert(j, V)
				break
		if len(ar) < n:
			ar.insert(i, V)
		printList(ar)
n = int(input())
ar = list(map(int, input().split()))
insertionSort(n, ar)


size = int(input())
ar = [int(word) for word in input().split(' ')]

def insertionSort(ar):
	for i in range(1, len(ar)):
		val = ar[i]
		index = i - 1
		while index >= 0 and val < ar[index]:
			ar[index + 1] = ar[index]
			ar[index] = val
			index -= 1
		print(' '.join(map(str, ar)))
insertionSort(ar)


def insertion_sort(l):
	for i in range(1, len(l)):
		j = i - 1
		key = l[i]
		while l[j] > key and j >= 0:
			l[j + 1] = l[j]
			j -= 1
		l[j + 1] = key
		print(' '.join([str(k) for k in l]))
	return l
s = int(input())
arr = [int(i) for i in input().split()]
insertion_sort(arr)


def printlist(x):
	string = ''
	for i in x:
		string += str(i) + ' '
	print(string.strip())

def insertElement(x):
	element = None
	for i in range(len(x) - 1, -1, -1):
		if element == None:
			if x[i] < x[i - 1]:
				element = x[i]
				x[i] = x[i - 1]
			else:
				return x
		elif element >= x[i - 1]:
			x[i] = element
			return x
		else:
			x[i] = x[i - 1]
	else:
		x[0] = element
		return x
x = input()
x = input()
x = x.split()
for i in range(len(x)):
	x[i] = int(x[i])
for i in range(2, len(x) + 1):
	x[:i] = insertElement(x[:i])
	printlist(x)


import sys
array = [int(x) for x in sys.stdin.readlines()[1].split()]
for x in range(1, len(array)):
	while x > 0 and array[x - 1] > array[x]:
		(array[x - 1], array[x]) = (array[x], array[x - 1])
		x -= 1
	print(' '.join((str(x) for x in array)))


def printArr(arr):
	for elt in arr:
		print(elt, end=' ')
	print()
n = int(input())
args = [int(i) for i in input().split()]
for i in range(1, n):
	if args[i] < args[i - 1]:
		toInsert = args[i]
		for j in range(i, 0, -1):
			if args[j - 1] > toInsert:
				args[j] = args[j - 1]
			else:
				args[j] = toInsert
				break
			if j == 1 and toInsert < args[j]:
				args[0] = toInsert
	printArr(args)


def insertion_sort(a):
	for i in range(1, len(a)):
		v = a[i]
		for j in range(i - 1, -1, -1):
			if a[j] > v:
				a[j + 1] = a[j]
			else:
				a[j + 1] = v
				break
		else:
			a[0] = v
		yield
size = input()
line = input()
line = [int(x) for x in line.split(' ')]
for iteration in insertion_sort(line):
	print(' '.join((str(x) for x in line)))


def strl(l):
	s = ''
	for i in l:
		s += str(i) + ' '
	return s[:-1]
n = int(input())
(a, *l) = map(int, ['1'] + input().split())
del a
for j in range(1, n):
	V = l[j]
	for i in range(j - 1, -1, -1):
		if l[i] > V:
			l[i + 1] = l[i]
			if i == 0:
				l[0] = V
				break
		else:
			l[i + 1] = V
			break
	print(strl(l))


s = input()
ar = input()

def insertion_sort(l, s):
	for i in range(1, s):
		insert(i, l)
		pp(l)

def insert(i, l):
	v = l[i]
	count = i
	while count != 0:
		if v < l[count - 1]:
			l[count] = l[count - 1]
			l[count - 1] = v
		count -= 1

def pp(l):
	s = ''
	for t in l:
		s += str(t) + ' '
	print(s.strip())
insertion_sort([int(i) for i in ar.split(' ')], int(s))


def in_loc(a, n):
	V = a[n]
	if n == 1:
		temp = a[0]
		a[0] = a[1]
		a[1] = temp
		return a
	for i in range(n - 1, -1, -1):
		if a[i] > V:
			a[i + 1] = a[i]
		else:
			a[i + 1] = V
			break
	if a[0] == a[1]:
		a[0] = V
	return a

def insertionSort(a, n):
	i = 1
	for i in range(1, n):
		if a[i] < a[i - 1]:
			a = in_loc(a, i)
		print(*a, sep=' ')

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	insertionSort(a, n)
main()


def sort(v, index):
	a = v[index]
	n = index - 1
	while n >= 0 and v[n] > a:
		v[n + 1] = v[n]
		n -= 1
	if n == -1:
		v[0] = a
	else:
		v[n + 1] = a
	print(*v, sep=' ')
size = int(input())
v = [int(i) for i in input().strip().split()]
for i in range(1, size):
	sort(v, i)


s = int(input())
c = input().strip().split(' ')

def insertionSort(c):
	for i in range(s - 1):
		for k in range(i, -1, -1):
			if int(c[k + 1]) < int(c[k]):
				(c[k + 1], c[k]) = (c[k], c[k + 1])
		print(' '.join(c))
insertionSort(c)


s = int(input())
ar = [int(x) for x in input().split()]
if s == 1:
	print(ar[0])
else:
	for i in range(1, s):
		current = ar[i]
		i -= 1
		while ar[i] > current and i >= 0:
			ar[i + 1] = ar[i]
			i -= 1
		ar[i + 1] = current
		print(' '.join(map(str, ar)))


input()
nums = list(map(int, input().split()))
for count in range(len(nums) - 1):
	for i in range(count, -1, -1):
		if nums[i] > nums[i + 1]:
			(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
	print(' '.join(map(str, nums)))


import fileinput
lines = fileinput.input()
size = int(lines[0])
ar = [int(x) for x in lines[1].rstrip().split(' ')]
for index in range(1, size):
	v = ar[index]
	subindex = index
	while not (v <= ar[subindex] and v > ar[subindex - 1]) and subindex != 0:
		subindex -= 1
	ar.insert(subindex, v)
	ar.pop(index + 1)
	print(format(' '.join(map(str, ar))))


import sys
x = int(input())
arr = input()
arr = list(map(int, arr.split()))
for i in range(1, x):
	newVal = arr[i]
	for j in range(i - 1, -1, -1):
		chkVal = arr[j]
		if newVal < chkVal:
			arr[j + 1] = chkVal
			if j == 0:
				arr[j] = newVal
		else:
			arr[j + 1] = newVal
			break
	print(' '.join((str(p) for p in arr)))


def insertion():
	size = int(input())
	inp_str = str(input().strip())
	inp_list = [int(x) for x in inp_str.split(' ')]
	for j in range(1, len(inp_list)):
		count = j
		element_v = inp_list[count]
		while count > 0 and element_v < inp_list[count - 1]:
			inp_list[count] = inp_list[count - 1]
			count = count - 1
			inp_list[count] = element_v
		print(' '.join((str(x) for x in inp_list)))

def main():
	insertion()
main()


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

def output(arr):
	print(' '.join(list(map(str, arr))))
for l in range(1, len(arr)):
	for i in range(l, 0, -1):
		if arr[i] < arr[i - 1]:
			tmp = arr[i]
			arr[i] = arr[i - 1]
			arr[i - 1] = tmp
	output(arr)


def insert(sortedar, item):
	for i in range(len(sortedar)):
		if sortedar[i] > item or sortedar == []:
			newar = sortedar[:i] + [item] + sortedar[i:]
			return newar
	sortedar.append(item)
	return sortedar

def sort(s, ar):
	unsortedar = ar
	item = unsortedar.pop(0)
	sortedar = [item]
	while unsortedar != []:
		item = unsortedar.pop(0)
		sortedar = insert(sortedar, item)
		strList = map(str, sortedar + unsortedar)
		print(' '.join(strList))
	return 0

def main():
	s = int(input())
	ar = list(map(int, input().rstrip().split()))
	sort(s, ar)
	return 0
main()


def print_vec(vec):
	print(' '.join(map(str, vec)))
nn = int(input())
vec = list(map(int, input().split()))
for i in range(1, len(vec)):
	value = vec[i]
	j = i - 1
	while j >= 0 and vec[j] > value:
		vec[j + 1] = vec[j]
		j -= 1
	if j + 1 != i:
		vec[j + 1] = value
	print_vec(vec)


def print_arr(arr):
	print(' '.join(map(str, arr)))
size = input()
arr = input().strip()
arr = list(map(int, arr.split(' ')))
for (i, start) in enumerate(arr[1:]):
	i += 1
	unsorted = arr[i]
	while True:
		if i == 0:
			arr[0] = unsorted
			print_arr(arr)
			break
		item = arr[i] = arr[i - 1]
		if item < unsorted:
			arr[i] = unsorted
			print_arr(arr)
			break
		i -= 1


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

def insertionSort(ar):
	for i in range(N):
		j = i
		while j > 0 and ar[j - 1] > ar[j]:
			(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
			j -= 1
		if i > 0:
			printArray(ar)

def printArray(array):
	for i in array:
		print(i, end=' ')
	print('')
insertionSort(array)


def insertionSort(ar):
	s = len(ar)
	for x in range(1, s):
		for y in range(x - 1, -1, -1):
			if ar[x] < ar[y]:
				t = ar[x]
				ar[x] = ar[y]
				ar[y] = t
				x = y
		print(*ar)
	return ''
input()
ar = [int(i) for i in input().strip().split()]
insertionSort(ar)


def insertion_sort(nums):
	if len(nums) == 1:
		print(nums[0])
	for i in range(1, len(nums)):
		j = i - 1
		while j != -1 and nums[j + 1] < nums[j]:
			(nums[j + 1], nums[j]) = (nums[j], nums[j + 1])
			j -= 1
		print(' '.join(map(str, nums)))
s = int(input())
ar = list(map(int, input().split()))
insertion_sort(ar)


def insertion_sort(list_ints):
	for i in range(1, len(list_ints)):
		key = list_ints[i]
		j = i - 1
		while j >= 0 and list_ints[j] > key:
			list_ints[j + 1] = list_ints[j]
			j = j - 1
		list_ints[j + 1] = key
		print(' '.join((str(x) for x in list_ints)))
a = int(input())
list_ints = [int(x) for x in input().strip().split(' ')]
insertion_sort(list_ints)


def insertionSort(ar):
	n = len(ar)
	for i in range(1, n):
		v = ar[i]
		for j in range(i, 0, -1):
			if ar[j - 1] > v:
				ar[j] = ar[j - 1]
			else:
				ar[j] = v
				break
		if v < ar[0]:
			ar[0] = v
		print_array(ar)

def print_array(ar):
	result = ''
	for el in ar:
		result += str(el) + ' '
	result += ''
	print(result)
m = input()
ar = [int(i) for i in input().strip().split()]
insertionSort(ar)


def insort(L):
	rev = list(enumerate(L))
	rev.reverse()
	for (i, e) in enumerate(L):
		if i == 0:
			continue
		insortp(L, i)
		o = map(str, L)
		print(' '.join(o))

def insortp(L, j):
	i = j
	e = L[j]
	while i > 0 and L[i - 1] > e:
		L[i] = L[i - 1]
		i -= 1
	L[i] = e
size = int(input().strip().split()[0])
lst = [int(j) for j in input().strip().split()]
insort(lst)


x = int(input(''))
ar = input('')
ar = ar.split(' ')
ar = [int(item) for item in ar]
narray = []
if len(ar) > 1:
	n = 2
	for y in range(0, x - 1):
		last = ar[n - 1]
		for i in range(1, n + 1):
			indice = n - (i + 1)
			if indice >= 0:
				previous = ar[n - (i + 1)]
				if previous > last:
					ar[n - i] = previous
				else:
					ar[n - i] = last
					narray = ' '.join((str(e) for e in ar))
					print(narray)
					break
			else:
				ar[0] = last
				narray = ' '.join((str(e) for e in ar))
				print(narray)
				break
		n = n + 1
else:
	narray = ' '.join((str(e) for e in ar))
	print(narray)


def show(ar):
	my_str = ''
	for i in range(0, len(ar) - 1):
		my_str += str(ar[i])
		my_str += ' '
	my_str += str(ar[len(ar) - 1])
	print(my_str)

def show_two_parts(ar, end):
	my_str = ''
	for i in range(0, len(ar) - 1):
		my_str += str(ar[i])
		my_str += ' '
	my_str += str(ar[len(ar) - 1])
	for i in range(0, len(end)):
		my_str += ' '
		my_str += str(end[i])
	print(my_str)

def shift(ar, i):
	ar[i + 1] = ar[i]
	return ar

def size_two(ar):
	if len(ar) < 2:
		return ar
	tmp = ar[1]
	if ar[0] > ar[1]:
		ar = shift(ar, 0)
		ar[0] = tmp
	return ar

def size_three(ar):
	if len(ar) < 3:
		return ar
	tmp = ar[2]
	if ar[1] > ar[2]:
		ar = shift(ar, 1)
		if ar[0] > tmp:
			ar = shift(ar, 0)
			ar[0] = tmp
		else:
			ar[1] = tmp
	return ar

def insertionSort(ar):
	if len(ar) < 1:
		return ar
	if len(ar) == 1:
		return ar
	if len(ar) == 2:
		size_two(ar)
		return ar
	if len(ar) == 3:
		size_three(ar)
		return ar
	tmp = ar[len(ar) - 1]
	for i in range(2, len(ar) + 1):
		if ar[len(ar) - i] > tmp:
			ar = shift(ar, len(ar) - i)
		else:
			break
	j = len(ar) - i
	while j < len(ar) and ar[j] <= tmp:
		j += 1
	if j < len(ar):
		ar[j] = tmp
	return ar

def sort_incrementally(ar):
	my_new_array = []
	end = []
	my_new_array.append(ar[0])
	for i in range(1, len(ar)):
		my_new_array.append(ar[i])
		my_new_array = insertionSort(my_new_array)
		end = []
		for j in range(i + 1, len(ar)):
			end.append(ar[j])
		show_two_parts(my_new_array, end)
m = input()
ar = [int(i) for i in input().strip().split()]
sort_incrementally(ar)


from bisect import bisect

def p(ar):
	print(' '.join(map(str, ar)))
input()
ar = [int(i) for i in input().split()]
if len(ar) == 1:
	p(ar)
for i in range(1, len(ar)):
	pos = bisect(ar, ar[i], 0, i)
	v = ar[i]
	del ar[i]
	ar[pos:pos] = [v]
	p(ar)


def printAr(ar):
	for j in ar:
		print(j, end=' ')
	print()

def insert(ar, n):
	a = ar[n - 1]
	for i in range(n - 2, -1, -1):
		if ar[i] > a:
			ar[i + 1] = ar[i]
		else:
			ar[i + 1] = a
			break
	else:
		ar[0] = a
	return ar
n = int(input())
ar = [int(num) for num in input().split()]
for i in range(2, n + 1):
	ar = insert(ar[:i], i) + ar[i:]
	printAr(ar)


import sys
var = sys.stdin.readline()
line = sys.stdin.readline()
varArray = line.split()
indexCount = 2
while indexCount <= int(var):
	subList = varArray[:indexCount]
	counter = 0
	for val in subList:
		subList[counter] = int(val)
		counter += 1
	subList.sort()
	innerLoopCount = 0
	for elm in subList:
		varArray[innerLoopCount] = elm
		innerLoopCount += 1
	indexCount += 1
	counter = 0
	for val in varArray:
		varArray[counter] = str(val)
		counter += 1
	print(' '.join(varArray))


def insertionSort(X):
	for i in range(2, len(X) + 1):
		print(' '.join((str(e) for e in sorted(X[:i]) + X[i:])))

def main():
	input()
	insertionSort([int(e) for e in input().split(' ')])
main()


def insertion_sort(array):
	for (i, x) in enumerate(array[1:]):
		for (j, y) in enumerate(array[:i + 1]):
			if y > x:
				array[j + 1:i + 2] = array[j:i + 1]
				array[j] = x
				break
		print(' '.join(('{}'.format(a) for a in array)))
	return array

def main():
	array_size = int(input())
	array = list(map(int, input().split()))
	insertion_sort(array)
main()


cases = int(input())
array = list()
i = 0
temp = ''
temp = input()
array = temp.split()
while i < cases:
	array[i] = int(array[i])
	i = i + 1
lenArray = len(array)
counter = 0
i = 1
while i < lenArray:
	j = i
	while j > 0 and array[j - 1] > array[j]:
		array[j - 1] = array[j - 1] + array[j]
		array[j] = array[j - 1] - array[j]
		array[j - 1] = array[j - 1] - array[j]
		counter = counter + 1
		j = j - 1
	outStr = ''
	for element in array:
		outStr = outStr + str(element) + ' '
	print(outStr)
	i = i + 1


def show_insertion_sort(L):
	for i in range(1, len(L)):
		val = L[i]
		j = i
		while j > 0 and L[j - 1] > val:
			L[j] = L[j - 1]
			j -= 1
		L[j] = val
		print(' '.join((str(e) for e in L)))
n = int(input())
L = [int(s) for s in input().split()]
show_insertion_sort(L)


def insertion_sort(array):
	for index in range(1, len(array)):
		val = array[index]
		i = index - 1
		while i >= 0:
			if val < array[i]:
				array[i + 1] = array[i]
				array[i] = val
				i -= 1
			else:
				break
		print(' '.join(map(str, array)))
n = int(input())
vals = [int(i) for i in input().split()]
insertion_sort(vals)


s = input().split()
ar = list(map(int, input().split()))
V = ar[len(ar) - 1]
sort = len(ar) - 1
for index in range(1, len(ar)):
	value = ar[index]
	i = index - 1
	while i >= 0:
		if value < ar[i]:
			ar[i + 1] = ar[i]
			ar[i] = value
			i = i - 1
		else:
			break
	print(*ar, sep=' ')


def insert(eli, i, arr):
	if i == eli:
		pass
	elif arr[eli] < arr[i]:
		buf = arr[i]
		arr[i] = arr[eli]
		for j in range(i + 1, eli + 1):
			buf2 = arr[j]
			arr[j] = buf
			buf = buf2
	else:
		insert(eli, i + 1, arr)

def pprint(arr):
	out = ''
	for i in range(len(arr)):
		out = out + str(arr[i]) + ' '
	print(out)
input()
arr = [int(x) for x in input().split()]
for i in range(1, len(arr)):
	insert(i, 0, arr)
	pprint(arr)


from bisect import bisect_left
n = int(input())
ar = list(map(int, input().split()))
if n < 2:
	print(ar[0])
	exit(0)
for i in range(1, n):
	v = ar[i]
	pos = bisect_left(ar, v, hi=i)
	if pos != i:
		ar[pos + 1:i + 1] = ar[pos:i]
		ar[pos] = v
	print(' '.join((str(x) for x in ar)))


import sys

def sort(array, index):
	for i in range(index - 1, -1, -1):
		if array[i] > array[index]:
			(array[i], array[index]) = (array[index], array[i])
			index -= 1
n = sys.stdin.readline()
arr = [int(x) for x in sys.stdin.readline().strip().split(' ')]
for i in range(1, len(arr)):
	sort(arr, i)
	print(' '.join([str(x) for x in arr]))


import sys

def print_list(data):
	for element in data:
		print(element, end=' ')
	print()
length = int(sys.stdin.readline())
data = []
raw = sys.stdin.readline().split()
for index in range(length):
	data.append(int(raw[index]))
for index in range(1, length):
	element = data[index]
	try:
		for pointer in range(index, 0, -1):
			if data[pointer - 1] < element:
				raise StopIteration('Place found!')
			data[pointer] = data[pointer - 1]
		data[0] = element
	except StopIteration:
		data[pointer] = element
	print_list(data)


s = int(input())
ar = list(map(int, input().split()))
for i in range(1, s):
	v = ar[i]
	for j in range(i, 0, -1):
		if v >= ar[j - 1]:
			ar[j] = v
			break
		ar[j] = ar[j - 1]
	else:
		ar[0] = v
	print(' '.join(map(str, ar)))


def insertionSort(ar):
	for i in range(1, len(ar)):
		V = ar[i]
		j = i
		while j > 0 and ar[j - 1] > V:
			ar[j] = ar[j - 1]
			j -= 1
		ar[j] = V
		print(' '.join([str(v) for v in ar]))
s = int(input())
ar = [int(v) for v in input().split()]
insertionSort(ar)


n = int(input())
array = [int(val) for val in input().split()]
for i in range(1, n):
	item = array[i]
	j = i
	while j > 0 and array[j - 1] > item:
		array[j] = array[j - 1]
		j -= 1
	array[j] = item
	[print(val, end=' ') for val in array]
	print()


def insertionSort(ar):
	for i in range(1, len(ar)):
		v = ar[i]
		while i > 0 and ar[i - 1] > v:
			ar[i] = ar[i - 1]
			i -= 1
		ar[i] = v
		print(' '.join(map(str, ar)))
m = int(input())
ar = [int(i) for i in input().split()]
insertionSort(ar)


size = int(input())
ar = list(map(int, input().split()))
for i in range(1, len(ar)):
	j = i
	while j >= 1 and ar[j] < ar[j - 1]:
		(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
		j -= 1
	print(*ar)


def insertionSort(ar):
	for index in range(1, len(ar)):
		curr = ar[index]
		scanning = index - 1
		while scanning >= 0 and ar[scanning] > curr:
			ar[scanning + 1] = ar[scanning]
			ar[scanning] = curr
			scanning -= 1
		print(' '.join((str(num) for num in ar)))
arr_size = input()
arr = [int(i) for i in input().strip().split()]
insertionSort(arr)


def insert(index):
	el = items[index]
	inserted = False
	for i in range(index - 1, -1, -1):
		if items[i] > el:
			items[i + 1] = items[i]
		elif items[i] == el:
			items[i + 1] = el
			inserted = True
			break
		else:
			items[i + 1] = el
			inserted = True
			break
	if not inserted:
		items[0] = el
	a = [str(x) for x in items]
	print(' '.join(a))
numitems = int(input())
line = input().split(' ')
items = [int(x) for x in line]
if len(items) > 0:
	el = items[len(items) - 1]
else:
	print('Empty Array')
if len(items) == 1:
	print(items)
	exit()
else:
	for i in range(1, len(items)):
		insert(i)


import sys

def mToString(mArray):
	startStr = ''
	for el in mArray:
		startStr = startStr + str(el) + ' '
	return startStr[:-1]

def insertToArrayWithElement(numArray, myElementIndex):
	lastNum = numArray[myElementIndex]
	lastNumIndex = myElementIndex
	while lastNumIndex > 0 and lastNum < numArray[lastNumIndex - 1]:
		numArray[lastNumIndex] = numArray[lastNumIndex - 1]
		lastNumIndex = lastNumIndex - 1
	numArray[lastNumIndex] = lastNum
	print(mToString(numArray))
lines = []
for line in sys.stdin:
	lines.append(line)
arrayLen = int(lines[0])
numArray = list(map(int, lines[1].split()))
for i in range(1, arrayLen):
	insertToArrayWithElement(numArray, i)


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

def insertionsort(ar):
	for i in range(1, len(ar)):
		j = i
		while j > 0 and ar[j - 1] > ar[j]:
			(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
			j = j - 1
		print(' '.join([str(x) for x in ar]))
insertionsort(ar)


s = int(input())
ar = [int(x) for x in input().split()]
for i in range(1, s):
	t = ar[i]
	for j in range(i - 1, -1, -1):
		if t < ar[j]:
			ar[j + 1] = ar[j]
		else:
			ar[j + 1] = t
			print(' '.join((str(x) for x in ar)))
			break
	else:
		ar[j] = t
		print(' '.join((str(x) for x in ar)))


def insertionSort(m, ar):
	if m < 2:
		print(' '.join([str(x) for x in ar]))
	for index in range(1, m):
		while ar[index] < ar[index - 1]:
			(ar[index], ar[index - 1]) = (ar[index - 1], ar[index])
			if index > 1:
				index -= 1
		print(' '.join([str(x) for x in ar]))
m = int(input())
ar = [int(i) for i in input().strip().split()]
insertionSort(m, ar)


s = int(input())
ar = list(map(int, str(input()).split()))
for i in range(1, s):
	v = ar[i]
	for j in range(i, 0, -1):
		if v < ar[j - 1]:
			ar[j] = ar[j - 1]
		else:
			break
	else:
		j = 0
	ar[j] = v
	print(' '.join(map(str, ar)))


__author__ = 'smuralid'
import sys

def insertion_sort(ar, s):
	v = ar[s - 1]
	j = 0
	for i in range(1, s):
		if ar[s - 1 - i] > v:
			ar[s - 1 - i + 1] = ar[s - 1 - i]
		else:
			ar[s - 1 - i + 1] = v
			return ar
			j = 1
			break
	if j == 0:
		ar[0] = v
		return ar
s = int(sys.stdin.readline().strip())
ar = [int(elem) for elem in sys.stdin.readline().split()]
sorted_array = []
for i in range(2, s + 1):
	print(str(insertion_sort(ar, i)).strip('[]').replace(',', ''))


def insert_sort(N):
	if len(N) == 1:
		return N
	for i in range(1, len(N)):
		k = N[i]
		j = i
		while j > 0 and N[j - 1] > k:
			N[j] = N[j - 1]
			j -= 1
		N[j] = k
		for l in N:
			print(l, end=' ')
		print('\r')
num = int(input())
ar = [int(c) for c in input().split()]
insert_sort(ar)


s = int(input())
iarr = [int(x) for x in input().split(' ')]

def printArr(arr):
	op = ''
	for x in arr:
		op = op + str(x) + ' '
	print(op)

def insert(arr):
	s = len(arr)
	v = arr[s - 1]
	for i in range(s - 2, -1, -1):
		if arr[i] > v:
			arr[i + 1] = arr[i]
			if i == 0:
				arr[0] = v
		else:
			arr[i + 1] = v
			break
	return arr
for e in range(1, s):
	iarr[:e + 1] = insert(iarr[:e + 1])
	printArr(iarr)