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

输出

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

样例输入

6
10 1 50 50 20 5

样例输出

3650