Background

Except for [Constraints and Specifications], this problem is exactly the same as P1090.

Problem Description

In an orchard, Duoduo has picked all the fruits and separated them into different piles according to their types. Duoduo decides to merge all the fruits into one pile.

In each merge, Duoduo can merge two piles of fruits into one, and the physical effort consumed equals the sum of the weights of the two piles. It can be seen that after $(n - 1)$ merges, there will be only one pile left. The total physical effort Duoduo spends while merging fruits equals the sum of the effort consumed in each merge.

Because Duoduo still needs to spend a lot of effort to carry these fruits home, Duoduo wants to save as much effort as possible when merging. Assume each fruit weighs $1$. Given the number of fruit types and the number of fruits of each type, your task is to design a merging order so that Duoduo’s total physical effort is minimized, and output this minimum effort value.

For example, there are $3$ piles of fruits with counts $1,~2,~9$. You can first merge the piles with $1$ and $2$ fruits, obtaining a new pile of size $3$ and consuming $3$ effort. Then merge this new pile with the original third pile, obtaining a new pile of size $12$ and consuming $12$ effort. Therefore, Duoduo’s total effort is $3+12=15$. It can be proven that $15$ is the minimum possible effort.

Input Format

The first line contains an integer $n$, representing the number of fruit piles.
The second line contains $n$ integers separated by spaces. The $i$-th integer represents the number of fruits in the $i$-th pile, $a_i$.

Output Format

Output one line containing one integer, representing the minimum physical effort.

3 
1 2 9 

15

Hint

[Constraints and Specifications]

This problem uses bundled multi-testpoint evaluation, with four subtasks in total.

• Subtask 1 (10 points): $1 \leq n \leq 8$.
• Subtask 2 (20 points): $1 \leq n \leq 10^3$.
• Subtask 3 (30 points): $1 \leq n \leq 10^5$.
• Subtask 4 (40 points): $1 \leq n \leq 10^7$.

For all testdata, it is guaranteed that $1 \leq a_i \leq 10^5$.

[Hints]

• Please note the impact of constant factors on program efficiency.
• Please use variables of suitable types to store the result of this problem.
• The input size of this problem is large, so please pay attention to input reading efficiency.

Translated by ChatGPT 5