let words str =
  let len = String.length str in
  let buf = Buffer.create 10 in
  let rec loop cont = function
      i when i = len -> cont [Buffer.contents buf |> int_of_string]
    | i ->
      loop
        (match str.[i] with
         | ' ' ->
           let v = Buffer.contents buf |> int_of_string in
           Buffer.clear buf; (fun x -> cont (v::x))
         | c ->
           Buffer.add_char buf c; cont)
        (i+1)
  in loop (fun x -> x) 0



let partition seq =
  let len = List.length seq in
  let rec loop l acc = function
      0 -> l,acc
    | i -> match l with
             []
           | [_] as l -> l,acc
           | h::t -> loop t (h::acc) (i-1)
  in loop seq [] len

let () =
  let n = read_int () - 1 in
  let l = read_line () |> words in
  let counter = ref 0 in
  let rec msort =
  let merge xs ys =
    let rec loop acc = function
        [],[] -> acc
      | xs,[] -> List.append (List.rev acc) xs
      | [],ys -> List.append (List.rev acc) ys
      | (x::xr as xs),(y::yr as ys) ->
         incr counter;
         if x<=y then loop (x::acc) (xr,ys) else loop (y::acc) (xs,yr)
    in loop [] (xs,ys)
  in
  function
    []
  | [_] as l -> l
  | l -> let l1,l2 = partition l in
         merge (msort l1) (msort l2)
  in
  List.iteri (fun i v -> Printf.printf (if i = n then "%d\n" else "%d ") v)
             (msort l);
  Printf.printf "%d\n" !counter