def merge_sort(array, left, right)
	return 0 unless left + 1 < right
	mid = (left + right) / 2
	compared_count  = merge_sort(array, left, mid)
	compared_count += merge_sort(array, mid, right)
	compared_count += merge(array, left, mid, right)
	compared_count
end

def merge(array, left, mid, right)
	left_array_size  = mid - left
	right_array_size = right - mid

	left_array  = []
	left_array_size.times { |i| left_array << array[left + i] }

	right_array = []
	right_array_size.times { |i| right_array << array[mid + i] }

	# 下記のループでの番兵をセット(最後は必ず片方がnilになるため)
	left_array  << Float::INFINITY
	right_array << Float::INFINITY

	compared_count = 0
	i = j = 0
	(left...right).each do |k|
		if left_array[i] <= right_array[j]
			array[k] = left_array[i]
			i += 1
		else
			array[k] = right_array[j]
			j += 1
		end
		compared_count += 1
	end
	compared_count
end

array_size = STDIN.gets.to_i
array = STDIN.gets.split[0...array_size].map(&:to_i)
compared_count = merge_sort(array, 0, array_size)
puts array.join(" ")
puts compared_count