let cnt = ref 0

let merge a l m r =
  let init_ary n p =
    Array.init (n + 1) (fun i -> if i = n then max_int else a.(p + i))
  in
  let ai = init_ary (m - l) l in
  let aj = init_ary (r - m) m in
  let rec doit i j k =
    if k < r then begin
      incr cnt;
      if ai.(i) <= aj.(j) then (a.(k) <- ai.(i); doit (i + 1) j (k + 1))
      else (a.(k) <- aj.(j); doit i (j + 1) (k + 1))
    end
  in
  doit 0 0 l

let rec merge_sort a l r =
  if (l + 1) < r then begin
    let m = (l + r) / 2 in
    merge_sort a l m;
    merge_sort a m r;
    merge a l m r
  end

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> Scanf.scanf "%d " (fun i -> i)) in
  merge_sort a 0 n;
  Array.iteri (fun i e -> if i <> 0 then print_string " "; print_int e) a;
  print_newline ();
  Printf.printf "%d\n" !cnt