import           Control.Applicative
import           Control.Monad
import           Debug.Trace

splitMid :: [Int] -> ([Int], [Int])
splitMid xs = splitAt mid xs
  where
    mid = length xs `div` 2

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

mergeSort :: [Int] -> [Int]
mergeSort xs
    | length r == 1 = merge l r
    | otherwise     = merge (mergeSort l) (mergeSort r)
  where
    (l, r) = splitMid xs

merge' :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
merge' (xs, p) ([], 0) = (xs, p)
merge' ([], 0) (ys, q) = (ys, q)
merge' (x:xs, p) (y:ys, q)
    | x <= y =
        let (zs, r) = merge' (xs, 0) (y : ys, 0)
         in (x : zs, p + q + r + 1)
    | otherwise =
        let (zs, r) = merge' (x : xs, 0) (ys, 0)
         in (y : zs, p + q + r + 1)

mergeSort' :: [Int] -> ([Int], Int)
mergeSort' xs
    | length r == 1 = merge' (l, length l) (r, length r)
    | otherwise = merge' (mergeSort' l) (mergeSort' r)
  where
    (l, r) = splitMid xs

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

