第1题 修篱笆 查看测评数据信息 农夫约翰想修牧场周围的一小段篱笆。他测量了一下篱笆，发现他需要N（1≤ N≤ 200000）块木板，每块木板都有一些整数长度Li（1≤ N ≤ 100000）单位长度。然后，他买了一块长木板，长度刚好足以锯入N块木板（即长度是长度Li的总和）。FJ忽略了“切口”，即锯切时锯屑损失的额外长度；你也应该忽略它。

FJ烦恼地意识到，他没有用来锯木头的锯子，所以他带着这块长木板来到Don的农场，礼貌地问他是否可以借一把锯子。农场主Don是一位资本家，他不借给FJ一把锯子，而是提议向农场主约翰收取木板N-1次切割的费用。切割一块木头的费用正好等于它的长度。切割一块长度为21的木板需要21美分。

然后，农夫Don让FJ决定切割木板的顺序和位置。帮助FJ确定他能花多少钱来制作N块木板。FJ知道他可以按照不同的顺序切割木板，这将导致不同的费用，因为产生的中间木板的长度不同。

输入格式 第1行：一个整数N，木板的数量

第2..N+1行：每行包含一个整数，用于描述所需板材的长度

输出格式 第1行：一个整数：他进行N-1次削减必须花费的最低金额

输入/输出例子1 输入：

3

8

5

8

输出：

34

样例解释 他想把一块长度为21的木板切成8、5和8段。

原始板的尺寸为8+5+8=21。第一次切割成本为21美元，应用于将电路板切割成13和8的尺寸。第二次切割将花费13美元，并应用于将13美元切割成8美元和5美元。这将花费21+13=34。如果将21分为16和5，第二次削减将花费16美元，总计37美元（超过34美元）。