北邮复试上机题：赫夫曼编码

给出n个有权值的结点，构造赫夫曼树，输出所有这n个结点的权值与其赫曼编码长度（即该结点在所构造的赫曼树中的深度）的乘积的总和。

Input

第一行是一个正整数n，表示一共有n个结点。

第二行为n个整数，分别表示这n个结点的权值。

Output

输出所有这n个结点的权值与其赫曼编码长度的乘积的总和。

Sample Input

5

1 2 2 5 9

Sample Output

37-

Huffman coding

The product of the given n right nodes construct the Huffman tree, the output of all n-vertex weights and their Herman coding length (that is, the junction depth in the constructed Herman tree,). combined.

Input

The first line is a positive integer n represents a total of n nodes.

The second line of n integers, respectively, an n-vertex weights.

Output

Output of all n-vertex weights and their coding Herman length sum of the products.

Sample Input

5

12259

Sample Output

37