题目描述

有 $n$ 堆石子排成一排，第 $i$ 堆石子的数量为 $a_i$。

现在要将这 $n$ 堆石子合并成一堆。每次只能选择相邻的两堆石子合并成新的一堆，本次合并的代价为这两堆石子的数量之和。经过 $n-1$ 次合并后，所有石子会被合并成一堆。

请计算合并的总代价最小值。

输入格式

输入包含多组测试数据，读入到文件结束。

每组测试数据包含两行：

第一行包含一个整数 $n$，表示石子堆数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每堆石子的数量，相邻整数之间用一个空格分隔。

输出格式

对于每组测试数据，输出一行一个整数，表示最小总代价。

3
1 2 3
7
13 7 8 16 21 4 18

9
239

数据范围与提示

• $1 \le n \le 200$
• $1 \le a_i \le 500$