Ivan has _n_ different boxes. The first of them contains some balls of _n_ different colors.
Ivan wants to play a strange game. He wants to distribute the balls into boxes in such a way that for every _i_ (1 ≤ _i_ ≤ _n_) _i_\-th box will contain all balls with color _i_.
In order to do this, Ivan will make some turns. Each turn he does the following:
1. Ivan chooses any non-empty box and takes all balls from this box;
2. Then Ivan chooses any _k_ empty boxes (the box from the first step becomes empty, and Ivan is allowed to choose it), separates the balls he took on the previous step into _k_ non-empty groups and puts each group into one of the boxes. He should put each group into a separate box. He can choose either _k_ = 2 or _k_ = 3.
The _penalty_ of the turn is the number of balls Ivan takes from the box during the first step of the turn. And _penalty_ of the game is the total _penalty_ of turns made by Ivan until he distributes all balls to corresponding boxes.
Help Ivan to determine the minimum possible _penalty_ of the game!
## Input
The first line contains one integer number _n_ (1 ≤ _n_ ≤ 200000) — the number of boxes and colors.
The second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109), where _a__i_ is the number of balls with color _i_.
## Output
Print one number — the minimum possible _penalty_ of the game.
[samples]
## Note
In the first example you take all the balls from the first box, choose _k_ = 3 and sort all colors to corresponding boxes. Penalty is 6.
In the second example you make two turns:
1. Take all the balls from the first box, choose _k_ = 3, put balls of color 3 to the third box, of color 4 — to the fourth box and the rest put back into the first box. Penalty is 14;
2. Take all the balls from the first box, choose _k_ = 2, put balls of color 1 to the first box, of color 2 — to the second box. Penalty is 5.
Total penalty is 19.
Ivan 有 #cf_span[n] 个不同的盒子。第一个盒子中装有 #cf_span[n] 种不同颜色的球。
Ivan 想玩一个奇怪的游戏。他希望将球分配到各个盒子中，使得对于每个 #cf_span[i]（#cf_span[1 ≤ i ≤ n]），第 #cf_span[i] 个盒子中只包含颜色为 #cf_span[i] 的球。
为了实现这一目标，Ivan 将进行若干轮操作。每一轮他执行以下步骤：
每轮的 _惩罚_ 是他在该轮第一步中从盒子中取出的球的数量。游戏的 _惩罚_ 是 Ivan 将所有球分配到对应盒子之前所进行的所有轮次的惩罚之和。
请帮助 Ivan 确定游戏的最小可能 _惩罚_！
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200000]）——盒子和颜色的数量。
第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 表示颜色为 #cf_span[i] 的球的数量。
请输出一个数——游戏的最小可能 _惩罚_。
在第一个例子中，你从第一个盒子中取出所有球，选择 #cf_span[k = 3]，并将所有颜色的球分配到对应的盒子中。惩罚为 #cf_span[6]。
在第二个例子中，你进行了两轮操作：
总惩罚为 #cf_span[19]。
## Input
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200000]）——盒子和颜色的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 表示颜色为 #cf_span[i] 的球的数量。
## Output
请输出一个数——游戏的最小可能 _惩罚_。
[samples]
## Note
在第一个例子中，你从第一个盒子中取出所有球，选择 #cf_span[k = 3]，并将所有颜色的球分配到对应的盒子中。惩罚为 #cf_span[6]。在第二个例子中，你进行了两轮操作：
取出第一个盒子中的所有球，选择 #cf_span[k = 3]，将颜色为 #cf_span[3] 的球放入第三个盒子，颜色为 #cf_span[4] 的球放入第四个盒子，其余球放回第一个盒子。惩罚为 #cf_span[14]；
取出第一个盒子中的所有球，选择 #cf_span[k = 2]，将颜色为 #cf_span[1] 的球放入第一个盒子，颜色为 #cf_span[2] 的球放入第二个盒子。惩罚为 #cf_span[5]。总惩罚为 #cf_span[19]。
Let $ n $ be the number of boxes and colors. Let $ a_1, a_2, \dots, a_n $ be the number of balls of each color, initially all in box 1.
In each move, Ivan may:
- Select a non-empty box containing balls of multiple colors.
- Take **all** balls from that box (penalty = number of balls in the box).
- Distribute them into their respective target boxes (i.e., ball of color $ i $ goes to box $ i $).
The goal is to minimize the total penalty.
This is equivalent to the problem of **minimum cost to merge piles** where:
- Initially, all balls are in one pile (box 1).
- We wish to partition the multiset of balls into $ n $ singleton piles (each color in its own box).
- The cost of splitting a pile is equal to its size.
- We can split a pile into any number of sub-piles (not just binary splits).
This is a classic problem solvable by **Huffman coding** or **greedy merging in reverse**.
### Key Insight:
The process is equivalent to building a tree where:
- Each leaf corresponds to a color with weight $ a_i $.
- Each internal node corresponds to a merge (or split) operation.
- The cost is the sum of all internal node weights.
But note: **We start with one pile and split it**. The total penalty is the sum of the sizes of all piles ever taken during splits.
This is equivalent to the **minimum total cost to split** the initial pile into singletons, where splitting a pile of size $ s $ into $ k $ sub-piles costs $ s $, and the sub-piles are then split recursively.
This is dual to the **Huffman coding problem** for merging: the minimum cost to split is the same as the minimum cost to merge if we reverse the process.
Thus, the minimal total penalty equals the **total weight of the Huffman tree** built from the multiset $ \{a_1, a_2, \dots, a_n\} $, i.e., the sum of all internal nodes when merging the smallest two piles repeatedly until one remains.
But wait — in the **merging** version, we start with $ n $ piles and merge two at a time until one pile remains. The cost is the sum of the merged piles at each step.
In our case, we start with one pile and split until we have $ n $ piles. The total penalty is the sum of the sizes of the piles we split.
It turns out: **The minimal total penalty is equal to the total cost of the Huffman tree built from the $ a_i $'s**.
Why? Because the splitting tree is the reverse of the merging tree. The sum of the internal nodes (which is the penalty) is identical.
### Formal Statement:
Let $ a_1, a_2, \dots, a_n \in \mathbb{N}^+ $ be given.
Define $ T $ as the minimum total cost to merge $ n $ piles of sizes $ a_i $ into one pile, where the cost of merging two piles of sizes $ x $ and $ y $ is $ x + y $, and total cost is the sum of all merge costs.
Then the minimal penalty for the splitting game is exactly $ T $.
This is computed by:
- Use a min-heap (priority queue).
- Repeatedly extract two smallest elements $ x, y $, merge them with cost $ x+y $, and insert $ x+y $ back.
- Accumulate the cost.
The final accumulated sum is the minimal penalty.
### Mathematical Formulation:
Let $ S = \sum_{i=1}^n a_i $.
The minimal penalty is:
$$
\boxed{\sum_{\text{all internal nodes } v} \text{weight}(v)}
$$
where the tree is the Huffman tree for the multiset $ \{a_1, \dots, a_n\} $, built by repeatedly combining the two smallest weights.
This is computed algorithmically as:
Initialize a min-heap $ H $ with elements $ a_1, a_2, \dots, a_n $.
Initialize $ \text{penalty} = 0 $.
While $ |H| > 1 $:
- Extract minimum $ x = \text{heappop}(H) $
- Extract minimum $ y = \text{heappop}(H) $
- $ \text{penalty} \gets \text{penalty} + x + y $
- Insert $ x + y $ into $ H $
Return $ \text{penalty} $
---
**Final Answer (Formal Output):**
Given $ n \in \mathbb{N} $, and $ a_1, a_2, \dots, a_n \in \mathbb{N}^+ $, the minimum penalty is:
$$
\boxed{\sum_{k=1}^{n-1} (x_k + y_k)}
$$
where $ (x_1, y_1), (x_2, y_2), \dots, (x_{n-1}, y_{n-1}) $ are the pairs of smallest elements merged in sequence in the Huffman algorithm.