题目描述

现在有 $n$ 堆石子围成一环，第 $i$ 堆石子有 $a_i$ 个。

你每次可以合并相邻的两堆石子，合并后的新堆的石子数量为两堆石子数量的和。

你需要计算出合并所有石子成一堆的最小代价。

输入格式

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

第二行 $n$ 个整数 $a_i$，表示第 $i$ 堆石子的数量。

$(1\le n \le 200,1\le a_i\le 100)$

输出格式

一个整数，表示合并所有石子成一堆的最小代价。

样例输入

4
4 5 9 4

样例输出

43