SENTINEL = 20000000
$count = 0

def merge_sort(array, left, right)
  if left + 1 < right
    mid = (left + right) / 2
    merge_sort(array, left, mid)
    merge_sort(array, mid, right)
    merge(array, left, mid, right)
  end
end

def merge(array, left, mid, right)
  left_array, right_array = [], []
  left_index = mid - left
  right_index = right - mid
  0.upto(left_index - 1) { |i| left_array[i] = array[left+i] }
  0.upto(right_index - 1) { |i| right_array[i] = array[mid+i] }
  left_array[left_index], right_array[right_index] = SENTINEL, SENTINEL

  left_current_index, right_current_index = 0, 0
  left.upto(right - 1) do |i|
    $count += 1
    if left_array[left_current_index] <= right_array[right_current_index]
      array[i] = left_array[left_current_index]
      left_current_index += 1
    else
      array[i] = right_array[right_current_index]
      right_current_index += 1
    end
  end
end

def trace(array)
  puts array.join(' ')
end

n = $stdin.gets.chomp.to_i
array = $stdin.gets.chomp.split(' ').map(&:to_i)

merge_sort(array, 0, n)
trace(array)
puts $count