题目背景

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

题目描述

在某一天，Pichuu 有 $N$ 名顾客等待充电。Pichuu 可以同时为多部手机充电，每部手机的充电功率相同且恒定。然而，不同型号的手机电池容量不同，因此完全充满所需的时间也不同。第 $i$ 部手机需要 $T_i$ 分钟才能完全充满。

Pichuu 不会停止充电，直到所有手机都充满电。为了避免顾客等待过久，Pichuu 可以将顾客分成若干连续的组，然后按顺序为每组充电。每组中的顾客必须等待前面的组完成充电后，才能开始充电。

对于第 $k$ 组，组内充电所需的时间为该组中 $T_i$ 的最大值（记为 $M_k$）。第 $i$ 名顾客的总等待时间 $W_i$ 是他所在组及其之前所有组的充电时间之和：

其中，$G_i$ 表示第 $i$ 名顾客所属的组编号。

Pichuu 希望通过合理分组最小化顾客的总等待时间。你的任务是帮助 Pichuu 计算最小的总等待时间。

输入格式

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

输出格式

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

5
1 3 2 6 3

27

7
1 1 2 2 2 2 2

14

提示

【样例解释】

对于样例 #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$