题目描述

给定一个数字序列，每次可以合并两个相邻的数字a和b，合并后的得分是a+b。继续合并新产生的数字与其他相邻数字，直到所有数字合并成一个数为止。总得分是每次合并得分的总和。请计算合并成一个数的最大可能总得分。

输入描述

第一行包含一个整数n，表示数字序列的长度。 第二行包含n个整数，用空格分隔，表示该数字序列。

输出描述

输出一个整数，表示合并成一个数的最大总得分。

输入样例

4
1 3 5 2

输出样例

29

数据范围

1 ≤ n ≤ 100 序列中的每个数字均为正整数，且不超过1000