import Control.Applicative
import Control.Monad.State

main = do
    n <- readLn
    list <- map read.words<$>getLine :: IO [Int]
    let (list', cnt) = runState (mergeSort n list) 0
    putStrLn $ unwords.map show $ list'
    print cnt

merge :: (Ord a) => [a] -> [a] -> State Int [a]
merge xs [] = modify (+ length xs) >> return xs
merge [] ys = modify (+ length ys) >> return ys
merge (x:xs) (y:ys)
  | x <= y  = modify succ >> merge xs (y:ys) >>= \xs' -> return (x:xs')
  | otherwise = modify succ >> merge (x:xs) ys >>= \ys' -> return (y:ys')

mergeSort :: (Ord a) => Int -> [a] -> State Int [a]
mergeSort 0 [] = return []
mergeSort 1 [x] = return [x]
mergeSort n xs = do
    let nl = n `div` 2
        nr = n - nl
        (left, right) = splitAt nl xs
    sortedLeft <- mergeSort nl left
    sortedRight <- mergeSort nr right
    merge sortedLeft sortedRight

