小明在学习算法，现在他正在学习一种叫做Huffman树的数据结构。Huffman树在压缩数据、通信和加密等领域有着广泛的应用。 给出一数组pi=[p0, p1, ..., pn-1],用这个数组构造成一个Huffman树，过程如下: 1. 找到pi中最小的两个数,设为pa和pb,将pa和pb从pi中删除掉,然后将它们的和加入到pi中。这个过程的费用记为pa + pb。 2. 重复步骤1,直到pi中只剩下一个数。 在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。 请你编写一个程序，:对于给定的一个数组，输出构造Huffman树的总费用。 【输入描述】 输入两行 第一行输入整数n,表示数组的长度。 第二行n个整数,表示构成数组的元素，用空格隔开。

def huffman(n, arr):
    # 构造小根堆
    import heapq
    heap = arr[:]
    heapq.heapify(heap)

    cost = 0
    while len(heap) > 1:
        # 取出最小的两个数
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        # 将它们的和加入到堆中
        s = a + b
        cost += s
        heapq.heappush(heap, s)

    return cost

n = int(input())
arr = list(map(int, input().split()))
print(huffman(n, arr))

输入示例：

5
5 3 8 2 9

输出示例：

93