## 05 Oct Aurora Saturday 14:30 Python Practice 22.10.01.

**Question: **

There is an old stone game. At the beginning of the game the player picks n(1<=n<=50000) piles of stones in a line. The goal is to merge the stones in one pile observing the following rules:

At each step of the game, the player can merge two adjoining piles to a new pile. The score is the number of stones in the new pile.

You are to write a program to determine the minimum of the total score.

**Input**

The input contains several test cases. The first line of each test case contains an integer n, denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game.

The last test case is followed by one zero.

**Output**

For each test case output the answer on a single line. You may assume the answer will not exceed 1000000000.

Sample Input

1

100

3

3 4 3

4

1 1 1 1

0Sample Output

0

17

8

Sorry, the comment form is closed at this time.