A granary keeps n grain piles standing in a row, each with a positive integer size. You must combine them into a single pile by repeatedly picking two piles that are currently adjacent in the row and merging them into one pile whose size is the sum of the two. Each merge costs exactly the size of the newly formed pile.
Different merge orders can lead to different total costs. Report the minimum total cost to reduce the whole row to one pile.
Input format
Line 1: an integer n, the number of piles.
Line 2: n space-separated positive integers, the pile sizes from left to right.
Output format
A single integer: the minimum total merging cost (0 if there is only one pile).
Constraints
- 1 <= n <= 200
- 1 <= each pile size <= 1000