← 返回题目列表

Codeforces · 884/D

D. 盒子和球

中文机器翻译题面 查看原题

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。