题目描述

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

格式

输入格式

第一行包括牌数 \(N\)；

第二行包括 \(N\) 个\(1 \sim 100\)的整数，用空格分开。

输出格式

只有一个数字，即最小得分。

样例1

输入样例1

6
10 1 50 50 20 5

输出样例1

3650

限制

\(100\%\)的数据：\(3≤ n ≤100\)。