n = STDIN.gets.to_i
input = STDIN.gets.split.map(&:to_i)
@count = 0
def merge_sort(array)
  return array if array.size == 0
  return array if array.size == 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)
  merge(sorted_left, sorted_right)
end
def merge(left, right)
  result = []
  until left.empty? && right.empty? do
    @count += 1
   if left.empty?
     result << right.shift
   elsif right.empty?
     result << left.shift
   elsif left[0] < right[0]
     result << left.shift
   else
     result << right.shift
   end
  end
  result
end
puts merge_sort(input)*" "
p @count

