乘法游戏是在一行牌上进行的。

每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第$1$张和最后$1$张牌。

最后一次移动后，这里只剩下两张牌。你的目标是使得分的和最小。

例如，如果数是$10$、 $1$ 、$50$、 $20$ 、$5$

• 依次拿$1$、$20$、$50$，总分是:$10 \times 1 \times 50+50 \times 20 \times 5+10 \times 50 \times 5=8000$

• 而拿$50$、$20$、$1$，总分是$1 \times 50 \times 20+1 \times 20 \times 5+10 \times 1 \times 5=1150$。

输入格式

输入文件的第一行包括牌数($3 \lt n \leq 100$)，第二行包括$N$个$1 \cdots 100$的整数，用空格分开。

输出格式

输出文件只有一个数字：最小得分

样例

样例输入

6
10 1 50 50 20 5

样例输出

3650

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$65536\mathrm{KB}$