Boxes And Balls

题意翻译

你有 $n$ 个盒子和 $n$ 种颜色的球，第 $i$ 种颜色的球的数量是 $a_i$。 起初所有球都在第 $1$ 个盒子里，你希望让所有第 $i$ 种颜色的球都在第 $i$ 个盒子里。 于是你打算进行一系列操作。每次操作可以取出某个盒子中的所有球，腾空该盒子，但要扣除等于取出球数的点数，然后分成 $2$ 或 $3$ 组，将每组放到一个空盒子中。 求达到目标最少需要扣除的点数。

题目描述

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!

输入输出格式

输入格式

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}<=10^{9} $ ), where $ a_{i} $ is the number of balls with color $ i $ .

输出格式

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

输入输出样例

输入样例 #1

3
1 2 3

输出样例 #1

6

输入样例 #2

4
2 3 4 5

输出样例 #2

19

说明

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 $ .