# require 'benchmark'

# result = Benchmark.realtime do

  def divide_sort(array)
    # @count += 1
    length = array.length

    if length <= 1
      return array
    end

    left_array = divide_sort(array[0..((length-1)/2)])
    right_array = divide_sort(array[((length+1)/2)..(length-1)])
    i = 0

    while i < length do
      if left_array[0] < right_array[0]
        @count += 1
        array[i] = left_array.shift
        else
          @count += 1
          array[i] = right_array.shift
      end

      i += 1
      if left_array.length == 0
        while i < length do 
          @count += 1
          array[i] = right_array.shift
          i += 1
        end

      elsif right_array.length == 0
        while i < length do
          @count += 1
          array[i] = left_array.shift
          i += 1
        end
      end
    end
    return array
  end
# end
@count = 0
# buffer = []
array_num = gets.to_i
array = gets.to_s.split(" ").map(&:to_i)

# @count += 1

buffer = divide_sort(array)

# merge_sort(new_array_left,new_array_right)

# puts "処理概要 #{result}s"

puts buffer.join(" ")
puts @count
