题目描述

在仙女座某星系中发现一种微生物，这种生物可以在条件合适的情况下进行合并，每次合并时只能两个生物合并成一个生物，合并后体重为两个生物的体重总和，目前小童已经研制出可以使这种生物合并的药剂，当给相邻的两个生物分别使用这种药剂，它们就可以合成一个新的生物。药剂的用量与每个生物的体重成正比，如：a生物体重为5，b生物体重为6，它们在合并时需要消耗11的药剂量。现在有一排生物，已知每个生物的体重，它们的位置关系无法改变，怎么样才能在最节省药剂的情况下，使它们变成一个生物。

输入格式

输入一个整数 n，表示一排生物的数量。 接下来 n 行，每行一个正整数，小于 10000，分别表示第 i 个生物的体重 (1≤i≤n)。

输出格式

输出最小消耗的药剂量。

3
2
3
5

15

提示

2≤n≤100