Minimum Cost to Join Track Segments

You are given N track segments, each with a specified length. Your task is to connect all these segments into one continuous segment. The cost of joining two segments is equal to the sum of their lengths. Your goal is to minimize the total cost incurred by connecting these segments.

When two segments of lengths \(L_1\) and \(L_2\) are joined, the cost is \(L_1 + L_2\), and the resulting segment has length \(L_1 + L_2\). This newly formed segment may then be joined with other segments. The problem is to determine the minimum total cost to combine all the segments into one.

Constraints:

• \(N \geq 1\)
• Each segment's length is a non-negative integer.

Example: For \(N = 4\) and segments [4, 3, 2, 6], the minimum total cost is 29.

inputFormat

The first line contains an integer (N), the number of segments. The second line contains (N) space-separated integers representing the lengths of the segments.

outputFormat

Output a single integer representing the minimum total cost to connect all the segments into one.## sample

4
4 3 2 6

29