@count = 0

def merge_sort(arr)
  return arr if arr.size == 1
  mid = arr.size / 2
  left, right = arr.slice(0, mid), arr.slice(mid, arr.size)
  merge(merge_sort(left), merge_sort(right))
end

def merge(arr1, arr2)
  ret = []
  until arr1.empty? || arr2.empty?
    @count += 1
    if arr1.first < arr2.first
      ret << arr1.shift
    else
      ret << arr2.shift
    end
  end

  until arr1.empty?
    @count += 1
    ret << arr1.shift
  end

  until arr2.empty?
    @count += 1
    ret << arr2.shift
  end

  ret
end

n = gets.to_i
arr = gets.split.map(&:to_i)
puts merge_sort(arr).join("\s")
puts @count