You have n sticks with given positive integer lengths. In one operation you pick any two sticks, remove them, and connect them into a single new stick whose length is the sum of the two lengths. The cost of that operation equals the length of the new stick. You repeat until a single stick remains.
Print the minimum possible total cost of combining all sticks into one. Because we ask for the minimum, the answer is unique. If there is only one stick, no operation is needed and the total cost is 0.
Input format
Line 1: an integer n.
Line 2: n space-separated positive integers, the stick lengths (this line is present even when n is 1).
Output format
A single integer: the minimum total cost.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ each length ≤ 100000