好的，这是整理后的完整题面，包含样例解释，格式清晰适合上传：

题目描述

有一个古老的石头游戏。
开始时，$n$ 堆石头排成一排。

游戏目标是将所有石头合并成一堆，规则如下：

1. 每一步可以将两堆相邻的石头合并成一堆新石头堆。
2. 每次合并的得分等于新堆中的石头数量。

你需要写一个程序，计算合并所有石头的最小总得分。

输入格式

输入包含多组测试数据。

• 每组数据第一行是一个整数 $n$。
• 第二行包含 $n$ 个整数，表示每堆石头的数量。
• 当输入一行只有一个 0 时，表示输入终止。

输出格式

对于每组测试数据，输出一行，表示最小总得分。

数据保证结果不超过 $10^9$。

数据范围

$1 \le n \le 50000$
每堆石头的数量是正整数，总和不超过 $10^9$。

输入样例

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

输出样例

0
17
8

样例解释

第一组数据

$n=1$，只有一堆石头，不需要合并，总得分为 0。
输出 0。

第二组数据

$n=3$，石头数量分别为 $3, 4, 3$。
最少得分的合并顺序：

1. 先合并 $3$ 和 $4$，得到 $7$，得分 $7$；堆变为 $7, 3$。
2. 再合并 $7$ 和 $3$，得到 $10$，得分 $10$。
   总得分 $7 + 10 = 17$。

其他顺序可能会得到更大的得分，比如：

• 先合并 $4$ 和 $3$ 得 $7$，得分 $7$；堆变为 $3, 7$。
• 再合并 $3$ 和 $7$ 得 $10$，得分 $10$。总得分也是 $17$。
  实际上对于 $[3,4,3]$，最小得分就是 17。

输出 17。

第三组数据

$n=4$，每堆 $1$ 个石头，石头数组 $[1,1,1,1]$。
最少得分的合并顺序（类似哈夫曼合并）：

1. 合并前两个 $1$，得 $2$，得分 $2$；堆变为 $2,1,1$。
2. 合并后两个 $1$，得 $2$，得分 $2$；堆变为 $2,2$。
3. 合并两个 $2$，得 $4$，得分 $4$。
   总得分 $2 + 2 + 4 = 8$。

输出 8。

注意：由于 $n$ 可能很大（$n \le 50000$），不能使用 $O(n^3)$ 的区间 DP，需要更高效的算法（如 Garsia-Wachs 算法）来解决此题。