该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目背景】

甜品店正准备制作招牌混合糖，店员已将不同口味的糖果按种类分成了独立糖堆。为了得到最终的一大份混合糖，需要通过多次混合操作：每次只能将两堆糖果合并为一堆，且合并时消耗的搅拌能量等于两堆糖果的数量之和。现需通过 n-1 次合并最终得到一堆混合糖，为了节省成本，需设计最优的合并顺序，使总搅拌能量消耗最少。

【题目描述】

已知糖果的种类数 n，以及每种糖果对应的糖堆数量（每个糖果重量均为 1，糖堆数量即对应总重量）。请计算合并所有糖堆为一堆时，最少需要消耗的总搅拌能量。

例如：有 3 种口味的糖果，糖堆数量依次为 1、2、9。最优合并方案为：

1. 先合并数量 1 和 2 的两堆，得到新堆数量 3，消耗搅拌能量 3；
2. 再将新堆与数量 9 的堆合并，得到最终堆数量 12，消耗搅拌能量 12； 总消耗能量 = 3 + 12 = 15，此为最小消耗值。

【输入格式】

共两行：

1. 第一行是整数 n（1 ≤ n ≤ 10⁴），表示糖果的种类数；
2. 第二行包含 n 个整数，用空格分隔，第 i 个整数 aᵢ（1 ≤ aᵢ ≤ 2×10⁴）表示第 i 种糖果的糖堆数量。

【输出格式】

一个整数，即最小的总搅拌能量消耗值（输入数据保证该值小于 2³¹）。

【输入输出样例】

输入 #1

3
1 2 9

输出 #1

15

【说明/提示】

• 对于 30% 的数据，保证 n ≤ 10³；
• 对于 50% 的数据，保证 n ≤ 5×10³；
• 对于全部的数据，保证 n ≤ 10⁴。