P11333 [NOISG 2020 Finals] Discharging

为了成为最强的电力供应者，Pichuu 这只电鼠开启了一项新业务：使用他最爱的技能 Discharge 为顾客充电。由于业务的高效，Pichuu 每天都有许多顾客排队等待充电。

在某一天，Pichuu 有 $N$ 名顾客等待充电。Pichuu 可以同时为多部手机充电，每部手机的充电功率相同且恒定。然而，不同型号的手机电池容量不同，因此完全充满所需的时间也不同。第 $i$ 部手机需要 $T_i$ 分钟才能完全充满。 Pichuu 不会停止充电，直到所有手机都充满电。为了避免顾客等待过久，Pichuu 可以将顾客分成若干连续的组，然后按顺序为每组充电。每组中的顾客必须等待前面的组完成充电后，才能开始充电。 对于第 $k$ 组，组内充电所需的时间为该组中 $T_i$ 的最大值（记为 $M_k$）。第 $i$ 名顾客的总等待时间 $W_i$ 是他所在组及其之前所有组的充电时间之和： $$ W_i = \sum_{n=1}^{G_i} M_n $$ 其中，$G_i$ 表示第 $i$ 名顾客所属的组编号。 Pichuu 希望通过合理分组最小化顾客的总等待时间。你的任务是帮助 Pichuu 计算最小的总等待时间。

- 第一行包含一个整数 $N$，表示顾客数量。 - 第二行包含 $N$ 个整数，第 $i$ 个整数表示第 $i$ 部手机完全充电所需的时间 $T_i$。

- 输出一个整数，表示最小的总等待时间。

【样例解释】 对于样例 #1： - 最优分组为 $(1, 3, 2)$ 和 $(6, 3)$。两组的充电时间分别为 $3$ 和 $6$。 - 第一组的等待时间为 $3$（每名顾客），第二组的等待时间为 $3 + 6 = 9$（每名顾客）。 - 总等待时间为 $3 + 3 + 3 + 9 + 9 = 27$。 对于样例 #2： - 最优分组为一个整体，等待时间为 $2$（每名顾客）。 - 总等待时间为 $2 + 2 + 2 + 2 + 2 + 2 + 2 = 14$。 【数据范围】 - $1 \leq N \leq 10^6$ - $1 \leq T_i \leq 10^9$ | 子任务编号 | 分值 | 限制条件 | |:---:|:---:|:---:| | $1$ | $9$ | $1 \leq N \leq 3$ | | $2$ | $13$ | $1 \leq N \leq 1500$ 且 $T_i$ 非递减。 | | $3$ | $25$ | $T_i$ 非递减。 | | $4$ | $11$ | $T_i$ 非递增。 | | $5$ | $14$ | $1 \leq N \leq 1500$ | | $6$ | $28$ | 无额外限制。 |