let to_array s =
  Str.split (Str.regexp_string " ") s
  |> List.map int_of_string
  |> Array.of_list;;

let print_array l =
  Array.map string_of_int l
  |> Array.to_list
  |> String.concat " "
  |> print_endline;;

let merge (a:int array) left mid right =
  let n1 = mid - left and
      n2 = right - mid in
  let l = Array.init (n1+1) (fun i -> if i < n1 then a.(left+i) else max_int) and
      r = Array.init (n2+1) (fun i -> if i < n2 then a.(mid+i) else max_int) and
      i = ref 0 and
      j = ref 0 and
      count = ref 0
  in
  for k = left to right-1 do
    if l.(!i) <= r.(!j) then
      begin
        a.(k) <- l.(!i); i := !i+1
      end
    else
      begin
        a.(k) <- r.(!j); j := !j+1
      end;
    count := !count+1
  done;
  !count

let rec merge_sort a left right count =
  if left + 1 < right then
    let mid = (left+right)/2 in
    let count1 = merge_sort a left mid count and
        count2 = merge_sort a mid right count in
    count1 + count2 + (merge a left mid right)
  else count
;;

let () =
  let _ = read_int () and
      a = read_line () |> to_array in
  let count = merge_sort a 0 (Array.length a) 0 in
  print_array a;
  print_int count;
  print_newline ()
;;