题目描述

在一个果园里，多多已经将所有的果子打了下来，并且把所有的果子堆成了一堆。

现在多多要把这一堆果子分成 $n$ 堆。每一次分果子，多多可以选择一堆果子把它分成两堆果子，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $(n - 1)$ 次分堆之后， 就被分成 $n$ 堆了。多多在分果子时总共消耗的体力等于每次分果子所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在分果子时要尽可能地节省体力。假定每个果子重量都为 $1$，并且已知要分成的 $n$ 堆果子的每堆果子的数目，你的任务是设计出分果子的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如把一堆共 $12$ 个果子分成 $3$ 堆，数目依次为 $1,~2,~9$。可以先将开始的一堆 $12$ 分成 $3$ 和 $9$，耗费体力为 $12$；再把 $3$ 分成 $1$ 和 $2$，耗费体力为 $3$。所以多多总共耗费体力为 $12+3=15$。可以证明 $15$ 为最小的体力耗费值。

输入格式

输入的第一行是一个整数 $n$，代表果子要分成的堆数。

输入的第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表要分到第 $i$ 堆的果子的个数 $a_i$。

输出格式

输出一行一个整数，表示最小耗费的体力值。

样例输入

3 
1 2 9

样例输出

15

数据规模

共 $25$ 个测试点，保证 $1 ≤ n ≤ 10^7$， $1 \leq a_i \leq 10^5$。其中：

• $测试点 1-3，保证有 n ≤ 1000；$

• $测试点 4-5，保证有 n ≤ 5000；$

• $测试点 6-10，保证有 n = 10000。$

• $测试点 11-25，保证有 n ≤ 10^7。$