题目描述

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

你的目标是使得分的和最小。

例如，如果数是10 1  50  20  5，依次拿1、20、50，总分是  10150+50205+10505=8000

而拿50、20、1，总分是15020+1205+1015=1150。

输入格式

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

输出格式

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

样例

输入

6 

输出

10 1 50 50 20 5

3650

提示

对于$30 \%$的数据： $2 \le n \le 5$；

对于$60 \%$的数据：$2 \le n \le 20$；

对于$100 \%$的数据： $2 \le n \le 100；$