题目描述

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

输出格式

只有一个数字：最小得分。

6
10 1 50 50 20 5

3650

数据范围

$3 \le n \le 100$