题目描述

有 $n$ 堆石子排成一排，第 $i$ 堆石子有 $a_i$ 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？

输入格式

第一行一个数字 $n$。

接下来一行 $n$ 个整数 $a_1,a_2,…,a_n$。

输出格式

一行一个整数，表示答案。

Samples

3
1 2 3

9

4
4 4 2 5

30

数据规模

对于所有数据，保证 $1≤n,a_i≤500$。