该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

嘿啦啦啦，嘿啦啦，
天空出彩霞呀，
地上开红花呀，
中朝人民力量大，
打败那美国兵呀，
全世界人民拍手笑呀，
帝国主义害了怕呀。
嘿啦啦啦，嘿啦啦，
嘿啦啦啦，嘿啦啦，
全世界人民团结紧，
奋斗是力量。
嘿啦啦啦，嘿啦啦，
嘿啦啦啦，嘿啦啦，
天空出彩霞呀，
地上开红花呀，
全世界人民团结紧，
打败那美国兵呀......” 

打败国民党反动派，赶走美帝国主义纸老虎以后，全国人民兴高采烈，大家全心全意投入到建设新中国的战斗中去了，小花年满已经 18 岁，成为了一名铁路运输工人，由于国民 党在撤退在铁路沿线丢弃了很多箱武器枪械，今天，小花接到一个党组织下达的一个任务: 铁路沿线按顺序存放着的 N 堆装满枪械的箱子，组织上要求将箱子有次序的集中成一堆， 并且规定每次只能选相邻的 2 堆箱子合并成新的一堆，所需的运输费用与新的一堆中箱子的 数目成正比。现给定各堆箱子数，如果你对自己足够自信，请你帮助小花制定一个运输方案， 使总运输费用最低。设 N 堆箱子从左到右编号为 1、2、......N，各堆箱子数为 a1、a2、...... an。

Input Format

第一行:一个数 N。

第二行:N 个整数，表示每一堆的箱子数目 ai。

Output Format

一个数，即最小运输费用。

4
4 5 9 4

43

Hint

四边形不等式优化

Source

NOIP模拟 动态规划