测试数据来自 system/1181

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第 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。

【输入格式】

　　第一行包括牌数，第二行包括 \(n\) 个 \(1到100\) 之间的整数，用空格分开。

【输出格式】

　　只有一个数字：最小得分。

【输入输出样例】

　Input

6
10 1 50 50 20 5

　Output

3650

【数据限制】

　　\(3<=n<=100\)

【来源】

　　Mr.he