题目描述

太空梯的能量导轨上有$\red{n}$堆魔法石排成一排,其编号为$\red{1,2,3,...,n(n≤}$$\red{100)}$。每块魔 法石有一定的数量，例如有$\red{7}$堆魔法石，分别为$\red{13,7 ,8,16,21,4,18}$。

现在要将$\red{n}$堆魔法石归并成为一堆。归并的过程为每次只能将相邻的两堆魔法石堆成 一堆,这样经过$\red{n-1}$次归并后成为一堆,如上面的$\red{7}$堆魔法石,可以有多种方法归并成一 堆,其中的两种方法如图所示。

则$\red{(a)}$的归并代价为$\red{20+24+ 25+ 44+ 69 +87 = 267}$

$\red{(b)}$的归并代价为$\red{15+37 +22+28+ 59+ 87=248}$

可见不同的过程得到的归并代价是不一样的,现在请编程找出一种合理的方法,使归并 代价最小。

输入格式

第一行为一个整数$\red{n,}$且$\red{1<n≤}$$\red{100,}$表示有$\red{n}$堆沙子,第二行为$\red{n}$堆魔法石的数量。

输出格式

一个整数,即最小代价。

样例

输入样例1

7
13 7 8 16 21 4 18

输出样例1

239

输入样例2

10
12 3 13 7 8 23 14 6 9 34

输出样例2

398