合并展区

展厅中有 $n$ 个相邻展区，第 $i$ 个展区有 $a_i$ 件展品。

每次可以选择两个相邻的连续展区并将它们合并。若这两个连续展区中的展品总数分别为 $x$ 和 $y$，则本次合并代价为 $x+y$。合并后的新区仍与相邻展区保持原有顺序。

不断合并，直到只剩下一个展区。请计算最小可能的总代价。

第一行一个整数 $n$。

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

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

$1 \le n \le 500$。

$1 \le a_i \le 10^6$。