
n = STDIN.gets.to_i
input = STDIN.gets.split.map(&:to_i)

@count = 0

def merge_sort(array)
  # p "array: #{array}"
  return array if array.size == 0
  return array if array.size == 1
  @count += 1
  mid_index = array.size/2
  left = array[0..mid_index-1]
  right = array[mid_index..-1]
  sorted_left = merge_sort(left)
  sorted_right = merge_sort(right)
  result = []
  sorted_left.each do |i|
    while sorted_right[0] != nil && sorted_right[0] < i do
      @count += 1
      result << sorted_right[0]
      sorted_right.delete_at(0)
      break if sorted_right.size == 0
    end
    result << i
  end
  result = (result + sorted_right).flatten unless sorted_right.empty?
  result
end

puts merge_sort(input)*" "
p @count
