题目描述

这里有一个古老的石头游戏。

在游戏开始时，$\red {n}$ 堆石头摆成一排。

游戏目标是将石头合并成一堆，并遵守以下规则：

$\red { 1}$、在游戏的每个步骤中，玩家可以将两个相邻的石头堆合并为新的石头堆。

$\red 2$、每次合并的得分等于新堆中的石头数量。

你需要写一个程序判断，得分的最小值是多少。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含整数 $\red {n}$。

第二行包含$\red {n}$个整数，表示每堆石头的数量。

当输入一行为$\red {0}$时，表示输入终止。

输出格式

每组数据输出一个结果，每个结果占一行。

数据保证结果不超过$\red {10 ^9}$ 。

样例

输入样例

1
100
3
3 4 3
4
1 1 1 1
0

输出样例

0
17
8

提示

$\red {1≤n≤50000}$