题目描述

乘法谜题源自这样一个背景，我们有一行 $n$ 张牌，平铺在桌面上，每张牌的牌面上都标有一个正整数。

玩家的初始得分是 $0$，他接下来要进行 $n-2$ 次操作，每次操作他都需要从桌面上取出一张牌，然后他的得分会加上他取出的这张牌与取出的这张牌的左边的牌以及取出的这张牌的右边的牌的乘积。在第 $n-2$ 次操作结束后，桌面上将会只剩下两张牌。

你的目的是帮助玩家决定取牌的顺序，使得玩家的最终得分最小。

举个例子，如果一开始桌面上有 $5$ 张牌 $10, 1, 50, 20, 5$，如果玩家按照 $1,20,50$ 的顺序取，那么他的得分为：

$$10 \times 1 \times 50 + 50 \times 20 \times 5 + 10 \times 50 \times 5 = 500+5000+2500 = 8000$$

如果玩家按照 $50,20,1$ 的顺序取，那么他的得分为：

$$1 \times 50 \times 20 + 1 \times 20 \times 5 + 10 \times 1 \times 5 = 1000+100+50 = 1150$$

输入格式

输入的第一行包含一个整数 $N$ ，用于表示牌的数量（$3 \le N \le 100$）。 第二行包含 $N$ 个整数，用空格分隔，用于表示每张牌牌面上的数字，他的范围在 $1$ 到 $100$ 之间。

输出格式

输出一个整数，用于表示玩家的最小得分。

6
10 1 50 50 20 5

3650