def merge(a, left, mid, right)
  n1 = mid - left
  n2 = right - mid
  _L = a[left..mid-1]
  _R = a[mid..right-1]
  _L[n1] = _R[n2] = 1.0 / 0.0
  i = j = 0
  left.upto(right-1){|k|
    if _L[i] <= _R[j] then
      a[k] = _L[i]
      i += 1
    else
      a[k] = _R[j]
      j += 1
    end
  }
  return right - left
end

def mergeSort(a, left, right)
  count = 0
  if left+1 < right then
    mid = (left + right) / 2
    count += mergeSort(a, left, mid)
    count += mergeSort(a, mid, right)
    count += merge(a, left, mid, right)
  end
  return count
end

n = gets.to_i
a = gets.split.map(&:to_i)

count = mergeSort(a, 0, n)

puts a.join(" ")
puts count