题目描述

在一个圆形操场的四周摆放着 $n$ 堆石子，第 $i$ 堆石子的数量为 $a_i$。

现在要将石子有次序地合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

请计算将 $n$ 堆石子合并成一堆的最大得分。

输入格式

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

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每堆石子的数量。

输出格式

输出一行一个整数，表示最大得分。

4
4 4 5 9

54

数据范围与提示

• $1 \le n \le 2000$
• 1<=a[i]<=200

来源

动态规划，区间动归