module Main where

import Data.Functor ((<$>))
import Data.List (intercalate)

printList :: [Int] -> IO ()
printList = putStrLn . intercalate " " . map show

insert :: [Int] -> Int -> [Int]
insert [] x = [x]
insert (y:ys) x
  | x < y     = x:y:ys
  | otherwise = y:insert ys x

chattyInsertionSort :: [Int] -> IO ()
chattyInsertionSort [] = return ()
chattyInsertionSort (x:xs) = go [x] xs
  where
  go sorted [] = printList sorted
  go sorted (unsorted@(x:xs)) = do
    printList $ sorted ++ unsorted
    go (insert sorted x) xs

main = do
  -- Haskell doesn't need the number of elements, so drop it
  _ <- getLine
  xs <- map read . words <$> getLine
  chattyInsertionSort xs

