A technician has n fiber-optic segments with given positive integer lengths. Splicing two segments of lengths a and b costs a + b and produces a single segment of length a + b. Splicing continues until a single segment remains. You may choose the order of splices freely.
Report the minimum possible total splice cost. If there is only one segment to begin with, no splicing is needed and the cost is 0.
Input format
Line 1: an integer n.
Line 2: n space-separated positive integers, the segment lengths.
Output format
A single integer: the minimum total splice cost.
Constraints
- 1 <= n <= 100000
- 1 <= each length <= 1000000