Minimum Energy Consumption for Fruit Merging

In an orchard, Dodo has dropped all the fruits from the trees. The fruits have been divided into different heaps based on their types. Now, Dodo wants to merge all these heaps into a single heap.

The merging process is carried out by repeatedly combining two heaps into one. At each merge, the cost in energy is equal to the sum of the weights of the two heaps being merged. Since every fruit has a weight of 1, if a heap contains k fruits then its weight is k. After n-1 merge operations (where n is the number of initial heaps), only one heap remains.

Dodo wants to minimize the total energy expenditure. Your task is to determine the merge order that yields the minimum total energy cost, and output this minimal cost.

The total energy cost is the sum of the costs of each individual merge. For example, consider 3 heaps with fruit counts: 1, 2, and 9. By merging the first two heaps, we get a new heap of 3 fruits at a cost of 1+2=3. Next, merging this new heap with the third heap results in a heap of 12 fruits at a cost of 3+9=12. The total energy cost is 3+12=15, which is minimal in this case.

Note: All formulas must be rendered in \( \LaTeX \) format. For example, the number of merge operations is \( n-1 \).

inputFormat

The input consists of two lines:

• The first line contains a single integer \( n \) (\( 1 \leq n \leq 10^5 \)), representing the number of heaps.
• The second line contains \( n \) positive integers \( a_1, a_2, \dots, a_n \) (each \( 1 \leq a_i \leq 10^4 \)), where each \( a_i \) represents the number of fruits in the \( i\)-th heap.

outputFormat

Output a single integer, which is the minimum total energy cost needed to merge all the heaps into one.

sample

3
1 2 9

15