Stone Merging Game

You are given a row of N piles of stones arranged on a playground. You need to merge these piles into one single pile. The rule is that you can only merge two adjacent piles at a time. When you merge two piles, the number of stones in the new pile is the sum of the stones in the two original piles, and this sum is also counted as the score for that merge.

Your task is to design an algorithm to compute the minimum total score required to merge all N piles into one pile.

The scoring for each merge is given by the formula: \(score = \text{sum of stones in the two merged piles}\). If you merge piles with stone counts \(a\) and \(b\), the merge score is \(a+b\). The total score will be the sum of the scores of all individual merge operations.

inputFormat

The input consists of two lines:

• The first line contains an integer N representing the number of stone piles.
• The second line contains N space-separated integers, where each integer represents the number of stones in a pile.

outputFormat

Output a single integer representing the minimum total score to merge all stone piles into one.

sample

3
1 2 3

9