{-# LANGUAGE BangPatterns #-}

import           Control.Applicative
import           Control.Monad
import qualified Data.ByteString.Char8 as B

read' :: B.ByteString -> Int
read' bs | Just (n, _) <- B.readInt bs = n

merge :: [Int] -> [Int] -> ([Int], Int)
merge ls rs = go 0 [] ls rs
  where
    go !cnt !as [] [] = (reverse as, cnt)
    go !cnt !as xs [] = (reverse as ++ xs, cnt + length xs)
    go !cnt !as [] ys = (reverse as ++ ys, cnt + length ys)
    go !cnt !as (x:xs) (y:ys)
        | x <= y    = go (cnt + 1) (x:as) xs (y:ys)
        | otherwise = go (cnt + 1) (y:as) (x:xs) ys

mergeSort :: [Int] -> ([Int], Int)
mergeSort []  = ([], 0)
mergeSort [x] = ([x], 0)
mergeSort !xs = (ms, lc + rc + mc)
  where
    (ls, rs)  = splitAt (length xs `div` 2) xs
    (ls', lc) = mergeSort ls
    (rs', rc) = mergeSort rs
    (ms, mc)  = merge ls' rs'

main :: IO ()
main = do
    B.getLine
    !xs <- fmap read' . B.words <$> B.getLine
    let (ys, n) = mergeSort xs
    putStrLn . unwords $ fmap show ys
    print n

