Ivan 有 n 个不同的盒子。第一个包含一些 n 种不同颜色的球。
Ivan 想玩一个奇怪的游戏。他希望将球分配到盒子中,使得对于每个 i (1 ≤ i ≤ n),第 i 个盒子将包含所有颜色为 i 的球。
为了做到这一点,Ivan 将进行一些转弯。每个回合他都会执行以下操作:
1. Ivan 选择任意一个非空盒子,并取出该盒子中的所有球;
2.然后Ivan选择任意k个空盒子(第一步中的盒子变空,允许Ivan选择它),将他在上一步中拿走的球分成k个非空组,并将每组放入其中一个盒子中。他应该将每组放入单独的盒子中。他可以选择 k = 2 或 k = 3。
该回合的罚分是伊万在该回合第一步期间从禁区拿走的球数。比赛的罚分是伊万轮流罚分的总和,直到他将所有球分配到相应的盒子中为止。
帮助伊万确定比赛的最低可能罚分!
输入
第一行包含一个整数 n (1 ≤ n ≤ 200000) — 盒子和颜色的数量。
第二行包含n个整数a1, a2, ..., an (1 ≤ ai ≤ 109),其中ai是颜色为i的球的数量。
输出
打印一个数字——游戏可能受到的最小处罚。
示例
输入 #1
3 1 2 3
输出 #1
6
输入 #2
4 2 3 4 5
输出 #2
19
注意
在第一个示例中,您从第一个盒子中取出所有球,选择 k = 3 并将所有颜色排序到相应的盒子中。处罚是6分。
在第二个示例中,您转了两圈:
1.从第一个盒子中取出所有球,选择k = 3,将颜色3的球放入第三个盒子,颜色4的球放入第四个盒子,其余的放回第一个盒子。处罚为 14 分;
2. 取出第一个盒子中的所有球,选择 k = 2,将颜色 1 的球放入第一个盒子,颜色 2 的球放入第二个盒子。处罚为5分。
总罚分为 19。