Crystal Merging: Minimizing Total Cost

You are given n magical crystals, each with an associated magical power. Two crystals can be merged into one, and the cost of merging them is equal to the sum of their powers. This process continues until only one crystal remains. Your task is to determine the minimum total cost required to merge all the crystals into one.

It can be proven that a greedy algorithm using a minimum heap (priority queue) is optimal for this problem. In each step, merge the two crystals with the smallest powers, add their sum to the total cost, and push the merged crystal back into the heap. Repeat until only one crystal remains.

inputFormat

The first line contains a single integer n (2 ≤ n ≤ 10⁵), the number of crystals. The second line contains n space-separated integers representing the magical powers of the crystals.

outputFormat

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

4
4 3 2 6

29