You are given a sequence of length N. You can repeatedly choose any two numbers from the sequence and add them together, placing the sum back into the sequence, until only one number remains (thus, you will perform a total of N−1 additions).
Each addition has a cost, which is the sum of the two numbers chosen. For example, the cost of adding 1 and 10 is 11.
Your task is to add the N numbers together in such a way that the total cost is minimized.
Each test case starts with a positive integer N (2 ≤ N ≤ 200000), followed by N positive integers (each less than 100000).
print the minimum total cost of addition on a single line.
Remember to print a ‘\n’ at the end of the output.
To achieve the minimum total cost, always combine the two smallest available numbers first.
Note: The total cost may exceed 231 - 1
Initial: The initial sequence is {1, 2, 3}.
Step 1: We choose the numbers 1 and 2. After adding them, the sequence becomes {3, 3}, and the cost is 1+2=3.
Step 2: We choose the numbers 3 and 3. After adding them, the sequence becomes {6}, and the cost is 3+3=6.
Final: The total cost is 3+6=9.
Initial: The initial sequence is {1, 2, 3, 4}.
Step 1: We choose the numbers 1 and 2. After adding them, the sequence becomes {3, 3, 4}, and the cost is 1+2=3.
Step 2: We choose the numbers 3 and 3. After adding them, the sequence becomes {4, 6}, and the cost is 3+3=6.
Step 3: We choose the numbers 4 and 6. After adding them, the sequence becomes {10}, and the cost is 4+6=10.
Final: The total cost is 3+6+10=19.