Optimal Fruit Pile Merging

In a fruit orchard, all fruits are initially separated into distinct piles according to their types. Dodo wants to merge all these piles into one single pile. In each merge operation, you can combine any two piles. The cost (physical exertion) of merging two piles is equal to the sum of the weights (the number of fruits) in the two piles. Since each fruit weighs 1, the cost is just the sum of the fruit counts in the two piles.

After exactly $$n-1$$ merge operations, only one pile remains. Your task is to determine the order of merging such that the total cost is minimized, and output this minimum total cost.

Example:

For 3 fruit types with counts: 1, 2, 9, one optimal merging sequence is:

• Merge the piles with 1 and 2 fruits: cost = 1 + 2 = 3, new pile has 3 fruits.
• Merge the new pile (3 fruits) with the pile of 9 fruits: cost = 3 + 9 = 12.

Total minimum cost = 3 + 12 = 15.

inputFormat

The first line contains an integer $$n$$, representing the number of different fruit types (i.e. the number of piles).

The second line contains $$n$$ positive integers, where the \(i^{th}\) integer denotes the number of fruits in the \(i^{th}\) pile.

outputFormat

Output a single integer representing the minimum total cost (total physical exertion) required to merge all the fruit piles into one.

sample

3
1 2 9

15