珅泽教育的益智活动中摆放着 $N$ 堆史莱姆，每堆都有自己的大小。小泽每次只能选择相邻的两堆进行合并，新史莱姆的大小等于这两堆大小之和，而这次合并消耗的体力也等于新史莱姆的大小。

合并后，新史莱姆会留在原来的位置并继续与相邻堆参与后续合并，直到所有史莱姆合成一堆。不同的合并顺序会产生不同的总消耗，请计算完成全部合并所需的最小体力。

输入格式

第一行输入 $n$，第二行输入 $n$ 个正整数。

输出格式

输出最小总代价。

输入 #1

3
1 2 3

输出 #1

9

输入 #2

1
10

输出 #2

0

输入 #3

5
4 1 7 3 2

输出 #3

39

数据范围与约定

• 1 ≤ $n$ ≤ 80
• 1 ≤ $a_i$ ≤ $10^6$