当前没有测试数据。

题目背景

闵老师和李尧老师正在实验室整理一批实验器材箱。这些箱子排成一排，每个箱子的重量不同。由于存储空间限制，他们需要将所有箱子合并成一个箱子。但每次只能合并相邻的两个箱子，合并的代价是两个箱子重量之和（合并后的新箱子重量为两者之和）。总代价是所有合并步骤的代价总和。两位老师希望找到一种合并顺序，使得总代价最小。请你帮他们计算这个最小的总代价。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示器材箱的数量。
第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 100$），表示每个箱子的重量。

输出格式

输出一个整数，表示合并所有箱子的最小总代价。

样例输入

4  
1 3 5 2  

样例输出

22