题目描述

有 $n$ 堆石子排成一圈，第 $i$ 堆有 $a_i$ 个石子。每次可以选出相邻的两堆合并成一堆，得分是合并后这堆石子的数量。合并 $n-1$ 次之后只剩下一堆，请求出总得分的最小值。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1\sim a_n$，用空格隔开。

输出格式

一行一个整数，表示最小总得分。

输入输出样例 #1

输入 #1

4
4 4 5 9

输出 #1

43

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 200$，$1\le a_i\le 1000$。