题解 | #【模板】哈夫曼编码#

import heapq

def huffman_min_length(n, frequencies):
    # 使用优先队列（最小堆）来构建哈夫曼树
    heapq.heapify(frequencies)
    min_length = 0
    while len(frequencies) > 1:
        # 每次取出两个最小的频率
        freq1 = heapq.heappop(frequencies)
        freq2 = heapq.heappop(frequencies)
        # 合并后的新频率
        new_freq = freq1 + freq2
        # 将新频率放回优先队列
        heapq.heappush(frequencies, new_freq)
        # 增加编码长度
        min_length += new_freq
    return min_length

# 输入处理
n = int(input())
frequencies = list(map(int, input().split()))

# 计算哈夫曼编码的最短长度
min_length = huffman_min_length(n, frequencies)
print(min_length)