为了成为最强，电属性鼠标 Pichuu 自此开始了一项新业务，以更好地发挥他的特长：使用他最喜欢的招式“放电”（Discharge）来为顾客的手机充电。这是一项非常高效的业务，每天都有许多顾客光顾。
在特定的一天，Pichuu 有 $N$ 名顾客排队等待充电。他能够同时为多部手机充电，且每部手机分配到的电功率是相同且恒定的。当然，不同的手机型号具有不同的电池容量，因此充满电所需的时间也不同。具体来说，第 $i$ 部手机需要 $T_i$ 分钟才能充满电。
在放电时，Pichuu 在所有手机充满电之前不会停止。因此，为了避免触电，顾客必须等到最后一部手机充电完成后才能取回自己的手机。然而，并非毫无办法：为了最小化顾客的总等待时间，Pichuu 可以将他们分成任意数量的连续组，并按顺序为这些组充电。因此，每个组都必须等待前面的所有组充电完成，Pichuu 才能开始为该组的手机充电。
每位顾客都恰好属于一个组，其中第 $i$ 位顾客被分配到第 $G_i$ 组。设第 $k$ 组中 $T_i$ 的最大值为 $M_k$。因此，第 $i$ 位顾客的总等待时间 $W_i$ 将是其前面所有组以及他自己所在组的充电时间之和。（有关图示，请参考样例说明）
$$W_i = \sum_{n=1}^{G_i} M_n$$
为了最大化顾客满意度，Pichuu 希望最小化所有顾客等待时间的总和。 然而，Pichuu 只有老鼠般大小的大脑，无法计算出对顾客进行分组的最优方式。因此，他需要你的帮助来找到最优的分组方案，从而求出最小的等待时间总和。
输入格式
你的程序必须从标准输入中读取。
第一行包含一个整数 $N$，表示顾客的数量。
第二行包含 $N$ 个整数，其中第 $i$ 个整数表示为第 $i$ 位顾客的手机充电所需的时间 $T_i$。
输出格式
你的程序必须输出到标准输出。
输出应在单行中包含一个整数，表示最小可能的总等待时间。
实现细节
由于子任务 3、4 和 6 的输入长度可能非常大，建议你使用带有快速输入输出的 C++ 来解决此问题。科学委员会没有能够完全解决此问题的 Python 解决方案。
附件中提供了包含快速输入/输出模板的 C++ 和 Java 源文件。强烈建议你使用这些模板。
如果你使用 Java 实现解决方案，请将文件命名为 Discharging.java，并将主函数放在 Discharging 类中。
子任务
在每个测试点上，最大运行时间为 1.0s，最大内存使用量为 1GiB。对于所有测试用例，输入将满足以下范围：
- $1 \le N \le 10^6$
- $1 \le T_i \le 10^9$
你的程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 9 | $1 \le N \le 3$ |
| 2 | 13 | $1 \le N \le 1500$ 且 $T_i$ 单调不减 |
| 3 | 25 | $T_i$ 单调不减 |
| 4 | 11 | $T_i$ 单调不增 |
| 5 | 14 | $1 \le N \le 1500$ |
| 6 | 28 | 无 |
样例
输入样例 1
5 1 3 2 6 3
输出样例 1
27
样例说明 1
此测试用例适用于子任务 5 和 7。
最优方案是将顾客分成两个连续的组：$(1, 3, 2)$ 和 $(6, 3)$。这两组所需的时间分别为 $3$ 和 $6$，因为它们分别是各组中 $T_i$ 的最大值。第一组的每位顾客等待时间为 $3$，而第二组的每位顾客等待时间为 $3 + 6 = 9$，因为第二组必须等待第一组充电完成。因此，总等待时间为 $3 + 3 + 3 + 9 + 9 = 27$。
输入样例 2
7 1 1 2 2 2 2 2
输出样例 2
14
样例说明 2
此测试用例适用于子任务 2、3、5 和 6。
最优的分组方案是直接将所有顾客分在同一个组中，并同时为他们的手机充电。因此，该组所需的时间为 $2$。总等待时间将为 $2 + 2 + 2 + 2 + 2 + 2 + 2 = 14$。