CF884D.Boxes And Balls

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!

伊万有 $n$ 个互不相同的盒子。第一个盒子中装有 $n$ 种不同颜色的球。

伊万想玩一个奇特的游戏：他希望将这些球重新分配到各个盒子中，使得对每个 $i$（$1 \le i \le n$），第 $i$ 个盒子中恰好包含所有颜色为 $i$ 的球。

为此，伊万将进行若干轮操作。每轮操作中，他执行以下步骤：

1. 伊万任选一个非空盒子，并取出其中所有的球；
2. 然后，伊万任选 $k$ 个空盒子（注意：第一步中被取空的盒子此时已为空，伊万可以将其选入这 $k$ 个盒子之中），将上一步取出的所有球划分为 $k$ 个非空组，并将每一组分别放入这 $k$ 个盒子中的一个（即每组放入一个不同的盒子）。他只能选择 $k = 2$ 或 $k = 3$。

本轮操作的“代价”定义为第一步中伊万从盒子中取出的球的数量。而整局游戏的“总代价”则是伊万完成全部操作、最终使每个颜色 $i$ 的球全部落入第 $i$ 个盒子为止所经历的所有轮次的代价之和。

请帮助伊万求出该游戏可能达到的最小总代价！

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.

第一行包含一个整数 $ n $（$ 1 \leq n \leq 200000 $）—— 表示盒子与颜色的数量。

第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \leq a_i \leq 10^9 $），其中 $ a_i $ 表示颜色 $ i $ 的球的数量。

Print one number — the minimum possible penalty of the game.

输出一个数字——游戏的最小可能罚分。

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.

在第一个例子中，你取走第一个盒子中的所有球，选择 $k = 3$，并将所有颜色的球分别放入对应的盒子中。罚值为 6。

在第二个例子中，你进行两次操作：

1. 取走第一个盒子中的所有球，选择 $k = 3$，将颜色为 3 的球放入第三个盒子，颜色为 4 的球放入第四个盒子，其余球放回第一个盒子。罚值为 14；
2. 取走第一个盒子中的所有球，选择 $k = 2$，将颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子。罚值为 5。

总罚值为 19。