import Data.List
import Data.Functor
import Data.Monoid
import Control.Monad.Writer
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
readInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine :: IO [Int]


main :: IO()
main = do
  n <- readLn :: IO Int
  as <- readInts :: IO [Int]
  let (sorted, n) = runWriter $ mergeSortWithCount' as
  putStrLn . unwords . map show $ sorted
  print $ getSum n
  

mergeSortWithCount' :: (Ord a) => [a] -> Writer (Sum Int) [a]
mergeSortWithCount' (a:[]) = writer ([a], 0)
mergeSortWithCount' as = join $ liftM2 mergeM  (mergeSortWithCount' a) (mergeSortWithCount' b)
  where
    m = (length as) `div` 2
    (a, b) = splitAt m as 

mergeM :: (Ord a) => [a] -> [a] -> Writer (Sum Int) [a]
mergeM [] bs = writer (bs, Sum (length bs))
mergeM as [] = writer (as, Sum (length as))
mergeM (a:as) (b:bs) = if a < b
                       then mergeM as (b:bs) >>= (consCount a)
                       else mergeM (a:as) bs >>= (consCount b)

consCount :: a -> [a] -> Writer (Sum Int) [a]
consCount a as = writer (a:as, 1)

