描述

有一个古老的石子游戏。在游戏开始时，玩家挑选成一行的$n$（$1 \leq n \leq 50000$）堆石子。游戏目标是按照以下规则将这些石子合并成一堆：

在游戏的每一步，玩家可以将相邻的两堆石子合并成新的一堆。得分是新堆中石子的数量。

你需要编写一个程序来确定总得分的最小值。

输入

输入包含若干测试用例。每个测试用例的第一行包含一个整数$n$，表示石子堆的数量。接下来的$n$个整数描述了游戏开始时每堆石子的数量。

最后一个测试用例后面跟着一个$0$。

输出

对于每个测试用例，在单独一行输出答案。你可以假设答案不会超过$1000000000$。

输入数据 1

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

输出数据 1

0
17
8

来源

LouTiancheng@POJ