def printArray(arr):
    for x in arr:
        print(x, end=' ')
    print()

def insertionSort1(n, arr):
    i = n - 2
    lastElement = arr[n - 1]
    while(i >= 0 and arr[i] > lastElement):
        arr[i + 1] = arr[i]
        printArray(arr)
        i = i - 1
    arr[i + 1] = lastElement
    printArray(arr)