5792 - 乘法游戏

乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中,玩家拿出一张牌,得分是用它的数字乘以它左边和右边的数,所以不允许拿第1张和最后1张牌。最后一次移动后,这里只剩下两张牌。目标是使得分的和最小。

例如,如果数是10、1、50、20、5,依次拿1、20、50,总分是10*1*50+50*20*5+10*50*5=8000;而拿50、20、1,总分是1*50*20+1*20*5+10*1*5=1150。

输入

第1行1个整数n,表示牌数。

第2行包括n个1~100的整数,每两个数之间用一个空格分开。

输出

一行一个整数,表示最小得分。

样例

输入

6
10 1 50 50 20 5

输出

3650

提示

【数据规模】

对于30%的数据满足:2≤n≤5。

对于60%的数据满足:2≤n≤20。

对于100%的数据满足:2≤n≤100。

来源

课课通

时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题