题目描述

乘法谜题使用一排牌进行，每张牌上包含一个正整数。在每一步操作中，玩家从该行中抽出一张牌，得分等于被抽牌上的数字与左右相邻两张牌上的数字之积。不允许抽掉该排的第一张和最后一张牌。当排中只剩下两张牌时，游戏结束。

玩家的目标是通过选择合适的抽牌顺序，使得总得分最小。

例如，若牌上的数字为 10 1 50 20 5，玩家可以先抽 1，再抽 20，最后抽 50，得分计算如下：

• 抽 1：10 × 1 × 50 = 500
• 抽 20：50 × 20 × 5 = 5000
• 抽 50：10 × 50 × 5 = 2500

总得分为 500 + 5000 + 2500 = 8000。

如果按相反顺序抽牌，即先抽 50，再抽 20，最后抽 1，则得分为：

• 抽 50：1 × 50 × 20 = 1000
• 抽 20：1 × 20 × 5 = 100
• 抽 1：10 × 1 × 5 = 50

总得分为 1000 + 100 + 50 = 1150。

输入格式

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

输出格式

一个整数，表示能够获得的最小总得分。

输入输出样例

6
10 1 50 50 20 5

3650