该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

在操场上沿一直线排列着 $n$ 堆石子，每堆石子数为 $a_i$。

现要将石子有次序地合并成一堆。

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

允许在第一次合并前对调一次相邻两堆石子的次序。

计算在上述条件下将n堆石子合并成一堆的最小得分。

【输入格式】

第一行一个整数 $n \ (1 \le n \le 200)$；

第2行是顺序排列的各堆石子数 $a_i \ (0 \le a_i \le 20）$。

【输出格式】

输出合并的最小得分。

3
2 5 1

11

5
10 3 5 6 8

72