题目描述

有 $n$ 堆石子排成一排，第 $i$ 堆有 $a_i$ 个石子。现要将 $n$ 堆石子并成为一堆，每次只能将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过 $n-1$ 次合并后成为一堆。请你求出总的代价最小值。

输入格式

第一行有一个整数 $n$，表示有 $n$ 堆石子。

接下来的一行有 $n$ 个数，分别表示 $a_1\sim a_n$，用空格分隔。

输出格式

输出总代价的最小值。

输入输出样例

3
1 2 3

9

7
13 7 8 16 21 4 18

239

数据范围

对于 $10\%$ 的得分点：$0<n\le50$，$0\le a_i\le10^6$。

对于剩下 $90\%$ 的得分点：$0<n\le200$，$0\le a_i\le10^{15}$。