CF461A.Appleman and Toastman

Appleman and Toastman play a game. Initially Appleman gives one group of n numbers to the Toastman, then they start to complete the following tasks:

• Each time Toastman gets a group of numbers, he sums up all the numbers and adds this sum to the score. Then he gives the group to the Appleman.
• Each time Appleman gets a group consisting of a single number, he throws this group out. Each time Appleman gets a group consisting of more than one number, he splits the group into two non-empty groups (he can do it in any way) and gives each of them to Toastman.

After guys complete all the tasks they look at the score value. What is the maximum possible value of score they can get?

Appleman 和 Toastman 玩一个游戏。最初，Appleman 将一组包含 $n$ 个数的数组交给 Toastman，然后他们开始执行以下操作：

• 每当 Toastman 得到一组数时，他将这组中所有数求和，并将该和加到总分中；然后他将这组数交给 Appleman。
• 每当 Appleman 得到一组仅含一个数的数组时，他直接丢弃该组；每当 Appleman 得到一组包含多于一个数的数组时，他将该组任意划分为两个非空子组，并将这两个子组分别交给 Toastman。

当两人完成所有操作后，他们查看最终的总分。问：他们所能得到的最高可能总分是多少？

The first line contains a single integer n (1 ≤ n ≤ 3·105). The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 106) — the initial group that is given to Toastman.

第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$）——即初始时交给 Toastman 的数组。

Print a single integer — the largest possible score.

输出一个整数——最大的可能得分。

Consider the following situation in the first example. Initially Toastman gets group [3, 1, 5] and adds 9 to the score, then he give the group to Appleman. Appleman splits group [3, 1, 5] into two groups: [3, 5] and [1]. Both of them should be given to Toastman. When Toastman receives group [1], he adds 1 to score and gives the group to Appleman (he will throw it out). When Toastman receives group [3, 5], he adds 8 to the score and gives the group to Appleman. Appleman splits [3, 5] in the only possible way: [5] and [3]. Then he gives both groups to Toastman. When Toastman receives [5], he adds 5 to the score and gives the group to Appleman (he will throws it out). When Toastman receives [3], he adds 3 to the score and gives the group to Appleman (he will throws it out). Finally Toastman have added 9 + 1 + 8 + 5 + 3 = 26 to the score. This is the optimal sequence of actions.

考虑第一个例子中的以下情形。最初，Toastman 得到分组 $[3, 1, 5]$，并将该组元素之和 $9$ 加入总分，然后将该组交给 Appleman。Appleman 将分组 $[3, 1, 5]$ 拆分为两个分组：$[3, 5]$ 和 $[1]$，并将这两个分组都交给 Toastman。当 Toastman 收到分组 $[1]$ 时，他将 $1$ 加入总分，并将该分组交还给 Appleman（Appleman 将将其丢弃）。当 Toastman 收到分组 $[3, 5]$ 时，他将该组元素之和 $8$ 加入总分，并将该分组交还给 Appleman。Appleman 以唯一可能的方式将 $[3, 5]$ 拆分为 $[5]$ 和 $[3]$，然后将这两个分组都交给 Toastman。当 Toastman 收到 $[5]$ 时，他将 $5$ 加入总分，并将该分组交还给 Appleman（Appleman 将将其丢弃）。当 Toastman 收到 $[3]$ 时，他将 $3$ 加入总分，并将该分组交还给 Appleman（Appleman 将将其丢弃）。最终，Toastman 累计向总分中加入了 $9 + 1 + 8 + 5 + 3 = 26$。这是最优的操作序列。