CF884D Boxes And Balls

Ivan 有 $n$ 个不同的盒子。第一个盒子里有 $n$ 种不同颜色的若干球。 Ivan 想玩一种奇怪的游戏。他想要把球分配到各个盒子中，使得对于每个 $i$（$1 \leq i \leq n$），第 $i$ 个盒子只含有所有颜色为 $i$ 的球。 为此，Ivan 将进行若干次操作。每次操作包括以下两步： 1. Ivan 选择任意一个非空盒子，取出该盒子中的所有球； 2. 然后，Ivan 选择任意 $k$ 个空盒子（第 1 步取出球的盒子此时已被清空，允许选择它），把取出的球分成 $k$ 个非空的组，并将每一组放到一个盒子中，每个盒子只能放一组。他可以选择 $k=2$ 或 $k=3$。 每次操作的代价为 Ivan 在第一步从盒子里取出的球的数量。游戏的总代价是 Ivan 完成所有操作直到所有球分配到对应盒子为止的总代价之和。 请帮 Ivan 求出完成分配的最小总代价。

第一行包含一个整数 $n$（$1 \leq n \leq 200000$），表示盒子和颜色的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^{9}$），其中 $a_i$ 表示颜色 $i$ 的球的数量。

输出一个整数，表示完成分配的最小总代价。

在第一个样例中，可以取出第一个盒子中的所有球，选择 $k=3$，将各颜色的球分别放入对应的盒子。总代价为 $6$。 在第二个样例中，你可以分两步完成： 1. 取出第一个盒子的所有球，选择 $k=3$，将颜色 $3$ 的球放入第三个盒子，颜色 $4$ 的球放入第四个盒子，其余球放回第一个盒子。代价为 $14$； 2. 再从第一个盒子取出所有球，选择 $k=2$，把颜色 $1$ 的球放回第一个盒子，颜色 $2$ 的球放入第二个盒子。代价为 $5$。 总代价为 $19$。 由 ChatGPT 5 翻译