说明

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

输入格式

第一行包括牌数($3\leq n\leqslant 100$)

第二行包括$n$个1~100的整数，用空格分开

输出格式

一个数字：最小得分

样例

6
10 1 50 50 20 5

3650