题目描述

译自 NOISG 2020 Final T2. Discharging

为了成为最优秀的电老鼠，皮丘开始了一项更适合他特长的新生意：使用他最爱的技能放电来为顾客的手机充电。这项超级有效的生意每天吸引了许多顾客光顾。

在某一天，皮丘有 $N$ 名顾客排队等待为他们的手机充电。他可以同时为多部手机充电，每部手机获得的电力均等且恒定。当然，不同型号的手机具有不同的电池容量，因此充满电所需的时间各不相同。具体来说，第 $i$ 部手机需要 $T_i$ 分钟才能充满电。

在放电时，皮丘会持续充电直到所有手机都充满电。因此，为了避免被电击，顾客必须等到最后一部手机充满电后才能取回手机。然而，希望尚未完全丧失：为了最小化顾客的总等待时间，皮丘可以将顾客分成任意数量的连续组，然后按顺序为各组充电。因此，每组必须等待前面的组全部完成充电后，皮丘才能开始为该组的手机充电。

每位顾客恰好属于一个组，其中第 $i$ 位顾客被分配到第 $G_i$ 组。设第 $k$ 组中最大的 $T_i$ 为 $M_k$。因此，第 $i$ 位顾客的等待时间 $W_i$ 是他所在组之前的所有组以及他自己所在组的充电时间之和。（具体说明参见示例测试用例的解释）

为了最大化顾客满意度，皮丘希望最小化所有等待时间之和。

皮丘只有一个小小的老鼠大脑，无法计算出分组顾客的最佳方式。因此，他需要你的帮助来找到最佳分组方式，从而得到最小的总等待时间。

输入格式

程序需从标准输入读取数据。

第一行包含一个整数 $N$，表示顾客数量。

第二行包含 $N$ 个整数，其中第 $i$ 个整数表示为第 $i$ 位顾客的手机充电所需的时间 $T_i$。

输出格式

程序需向标准输出输出结果。

输出一行，包含一个整数，表示可能的最小总等待时间。

5
1 3 2 6 3

27

最优的分组方式是将顾客分为两个连续组：$(1, 3, 2)$ 和 $(6, 3)$。这两组的充电时间分别为 $3$ 和 $6$，因为它们分别是各组中最大的 $T_i$。第一组每位顾客的等待时间为 $3$，第二组每位顾客的等待时间为 $3 + 6 = 9$，因为第二组必须等待第一组完成充电。因此，总等待时间为 $3 + 3 + 3 + 9 + 9 = 27$。

7
1 1 2 2 2 2 2

14

最优分组方式是将所有顾客放在一个组中，同时为他们的手机充电。因此，该组的充电时间为 $2$。总等待时间为 $2 + 2 + 2 + 2 + 2 + 2 + 2 = 14$。

这个样例满足子任务 $2, 3, 5, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^6$
• $1 \leq T_i \leq 10^9$

详细子任务附加限制及分值如下表所示：