data Tree = Node Int Tree Tree | Empty
insertTree :: Tree -> Int -> Tree
insertTree Empty v = Node v Empty Empty
insertTree (Node v l r) i
  |v > i = Node v (insertTree l i) r
  |otherwise = Node v l (insertTree r i)

toList :: Tree -> [Int] -> [Int]
toList Empty list = list
toList (Node v l r) list = toList l (v:(toList r list))

sort :: [Int] -> [Int]
sort l = (((flip toList) []) . (foldl (insertTree) Empty)) l

mergeSort :: Int -> Int -> Int
mergeSort left right
  |left + 1 < right = (right - left) + mergeSort left mid + mergeSort mid right
  |otherwise = 0
  where
    mid = div (left + right) 2

join' :: (Show a) => Char -> [a] -> String
join' _ [a] = show a
join' c (h:t) = (show h) ++ (c:join' c t)

main :: IO ()
main = do
  n <- fmap (\m -> read m :: Int) getLine
  arr <- fmap (map (\m -> read m :: Int) . words) getLine
  putStrLn $ join' ' ' (sort arr)
  print $ mergeSort 0 n