Optimal Wooden Board Cutting

You are given an integer ( n ) representing the number of wooden boards you need, and a list of ( n ) positive integers ( l_1, l_2, \dots, l_n ) representing the lengths of the boards. You initially purchase one long board whose length is equal to ( \sum_{i=1}^{n} l_i ). Your goal is to cut this board into the ( n ) boards of the required lengths. Cutting a board of length ( x ) into two pieces consumes ( x ) units of energy. Since you need to make exactly ( n-1 ) cuts, determine the order in which to perform the cuts such that the total energy consumption is minimized.

The problem is equivalent to finding the minimum cost to merge the boards, where each merge of two boards of lengths ( a ) and ( b ) costs ( a+b ) energy. Use a greedy algorithm (similar to Huffman coding) to achieve the optimal solution.

inputFormat

The first line contains a single integer \( n \) (\( 2 \le n \le 10^5 \)), which is the number of boards.

The second line contains \( n \) space-separated positive integers \( l_1, l_2, \dots, l_n \) (\( 1 \le l_i \le 10^4 \)), representing the lengths of the boards.

You may assume that the sum of all \( l_i \) values fits into a 32-bit integer.

outputFormat

Output a single integer, the minimum total energy required to cut the board into \( n \) boards.

sample

3
5 2 4

17