题目描述

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

输入格式

第一行一个数字 $n$。

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

输出格式

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

Samples

3
1 3 2

9

数据规模

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