乘法游戏

题目描述

乘法游戏是在一行牌上进行的。每张牌上都有一个正整数。在每一次移动中，玩家拿出一张牌（不允许拿第 $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

6
10 1 50 50 20 5

输出样例 #1

3650

说明/提示

数据范围

• 对于 $30\%$ 的数据：$3 \le n \le 5$；
• 对于 $60\%$ 的数据：$3 \le n \le 20$；
• 对于 $100\%$ 的数据：$3 \le n \le 100$，每张牌上的数字为 $1 \sim 100$ 之间的正整数。