import Control.Applicative
import Control.Monad.State
import Data.Array.IO

main = do
  n <- getLine
  list <- map read.words<$>getLine :: IO [Int]
  res <- insertionSortIO list
  return ()
--  newListArray (1,n) list >>= insertionSortA

insertionSort [] = []
insertionSort [x] = [x]
insertionSort (x:xs) = insert x (insertionSort xs)
insert x []     = [x]
insert x (y:ys) = if x <= y then (x:y:ys)
                            else y : insert x ys

insertionSortA arr = do
  st <- fst<$>getBounds arr
  runStateT insertSteps (st,arr)

insertSteps :: StateT (Int,IOArray Int Int)  IO (IOArray Int Int)
insertSteps = do
  (i,arr) <- get
  (st, en) <- liftIO $ getBounds arr
  if i > en then return arr
            else do
              e <- liftIO $ readArray arr i
              liftIO $ insertA i arr e
              liftIO $ getElems arr >>= putStrLn.unwords.map show
              put (i+1,arr)
              insertSteps

insertA :: Ord e => Int -> IOArray Int e -> e -> IO ()
insertA i arr e = do
  (st,en) <- getBounds arr
  if i == st then writeArray arr i e
             else do
               e' <- readArray arr (i-1)
               if e' > e then do
                           writeArray arr i e'
                           insertA (i-1) arr e
                         else writeArray arr i e

insertionSortIO :: (Show a, Ord a) => [a] -> IO [a]
insertionSortIO xs = insertIO [] xs

insertIO acc [] = print acc >> return acc
insertIO acc (x:xs) = printState acc' xs >> insertIO acc' xs
    where acc' = insert x acc

printState xs1 xs2 = do
        putStr $ unwords.map show $ xs1
        putStr " "
        putStrLn $ unwords.map show $ xs2
