Optimal Parenthesizing for Minimal Intermediate Sum

You are given n numbers. Your task is to add exactly n-1 pairs of parentheses to determine the order of additions. When an addition is performed, an intermediate sum is produced. The total cost is defined as the sum of all n-1 intermediate results. Although addition is associative and the final sum is invariant, the cost (i.e. the sum of intermediate sums) depends on the order in which you perform the additions.

Objective: Determine the parenthesizing strategy (i.e. the order of pairwise additions) such that the total cost is minimized.

Example: For the numbers [1, 2, 3, 4], one optimal way is:

• Compute 1+2 = 3 (cost = 3), resulting in list [3, 3, 4].
• Then compute 3+3 = 6 (cost = 6), resulting in list [6, 4].
• Finally compute 6+4 = 10 (cost = 10).

Total cost = 3 + 6 + 10 = 19.

This problem is analogous to the optimal merging or Huffman coding strategy where the greedy technique of selecting the two smallest numbers to merge first will yield the minimal total cost.

inputFormat

The input consists of two lines:

1. The first line contains an integer n (n ≥ 2), representing the number of numbers.
2. The second line contains n space-separated integers.

outputFormat

Output a single integer which is the minimum total cost, computed as the sum of the n-1 intermediate sums when the additions are performed in the optimal order.

sample

2
10 20

30