题目描述

在一个操场上一排摆放着 $n$ 堆石子，第 $i$ 堆石子的数量为 $a_i$。

现在要将石子按顺序合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

请计算将 $n$ 堆石子合并成一堆的最小总得分。

输入格式

第一行包含一个正整数 $n$。

接下来 $n$ 行，每行包含一个正整数 $a_i$，表示第 $i$ 堆石子的数量。

输出格式

输出一行一个整数，表示最小总得分。

4
3
2
2
3

20

7
13
7
8
16
21
4
18

239

数据范围与提示

• $2 \le n \le 100$
• $1 \le a_i < 10000$