#描述#
有n堆石子排成一条直线，每堆石子有一定的重量。现在要合并这些石子成为一堆石子，但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力，该体力为所合并的两堆石子的重量之和。问最少需要多少体力才能将n堆石子合并成一堆石子？

#格式#
##输入格式##
输入只包含若干组数据。每组数据第一行包含一个正整数n(2&lt=n&lt=100)，表示有n堆石子。接下来一行包含n个正整数a1,a2,a3,...,an（0&ltai&lt=100，1&lt=i&lt=n）。

##输出格式##
对应输入的数据，每行输出消耗的体力。

#样例1#
##样例输入1##

2
47 95

##样例输出1##

142

#限制#
1000ms
32768KB

#提示#

#来源#
yaojian