在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2 堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。
设n堆货物从左到右编号为1，2，…，n。各堆货物集装箱数为a[1:n]。

对于给定n堆货物,计算合并成一堆的最少运输费用。

输入数据的第1 行是正整数n，表示有n堆货物。第2 行有n个数，分别表示每堆货物的集装箱数。

将计算出的最少运输费用输出