def merge_sort(arr, left, right)
  return 0 unless left + 1 < right

  count = 0

  mid = (left + right) / 2

  count += merge_sort(arr, left, mid)
  count += merge_sort(arr, mid, right)
  count += merge(arr, left, mid, right)

  count
end

def merge(arr, left, mid, right)
  n1 = mid - left
  n2 = right - mid

  left_arr = arr[left, n1]
  right_arr = arr[mid, n2]

  left_arr << Float::INFINITY
  right_arr << Float::INFINITY

  i = j = 0
  k = left
  count = 0

  while k < right
    if left_arr[i] <= right_arr[j]
      arr[k] = left_arr[i]
      i += 1
    else
      arr[k] = right_arr[j]
      j += 1
    end

    count += 1
    k += 1
  end

  count
end

if $PROGRAM_NAME == __FILE__
  n = gets.to_i

  arr = gets.chomp.split.map(&:to_i)

  count = merge_sort(arr, 0, n)

  puts arr.join(' ')
  puts count
end