对于给定的长度为 的数组 ，你可以选择两个相邻的元素 和 ，将它们相加合并为一个新元素，合并后与这两个元素相邻的元素将与新的这个元素相邻，合并的代价为这个新元素的值。 求解将全部 个元素合并为一个元素需要的最小代价。

输入描述:

第一行输入一个整数 代表数组中的元素数量。第二行输入 个整数 代表数组中的元素。

输出描述:

在一行上输出一个整数，代表将全部 个元素合并为一个元素需要的最小代价。