Description

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

Input

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

Output

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

Sample

Input

2
47 95

Output

142

Source: yaojian