import Control.Applicative
import Data.Array.IO

main = do
        n <- readLn
        arr <- newListArray (0,(n-1)) =<< map read.words<$>getLine :: IO (IOArray Int Int)
        printIOArray arr
        insertionSortShow n arr
        return ()

insert :: (MArray a e m, Ord e) => Int -> a Int e -> m (a Int e)
insert i arr = readArray arr i >>= \e -> searchPos e (i-1) arr

searchPos :: (MArray a e m, Ord e) => e -> Int -> a Int e -> m (a Int e)
searchPos e j arr
    | j < 0 = writeArray arr (j+1) e >> return arr
    | otherwise = do
        e' <- readArray arr j
        if e' > e then writeArray arr (j+1) e' >> searchPos e (j-1) arr
                  else writeArray arr (j+1) e >> return arr

insertionSort :: (MArray a e m, Ord e) => Int -> a Int e -> m (a Int e)
insertionSort n arr = foldl (>>=) (return arr) $ map insert [0..(n-1)]

insertionSortShow n arr = foldl (>>=) (return arr) $ map (\i arr -> insert i arr >>= printIOArray >> return arr) [1..(n-1)]

printIOArray :: (Show e) => IOArray Int e -> IO ()
printIOArray arr = getElems arr >>= putStrLn.unwords.map show