题目描述

在一条直线上摆着 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。每次只能把相邻的两堆合并成一堆，合并的代价是这两堆石子的总数。经过 $n-1$ 次合并后变成一堆。

求把所有石子合并成一堆的最小总代价。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

一行一个整数，表示最小总代价。

输入样例 1

4
1 3 5 2

输出样例 1

22

说明

最优方案之一：先合并 1+3（代价 4），再合并 5+2（代价 7），最后合并 4+7（代价 11），总代价 $4+7+11=22$。

贪心反例

石子序列： 9 4 6 1 5

贪心过程

最优方案（DP）

贪心 57 > 最优 56，差距虽小，但足以说明贪心不成立。

数据范围

$1 \le n \le 200$，$1 \le a_i \le 1000$。