题目描述

乘法游戏在一行牌上进行。每张牌上都有一个正整数。

每一次移动中，玩家拿出一张牌，但不允许拿第 $1$ 张和最后 $1$ 张牌。拿出一张牌时，得分为这张牌上的数字乘以它左边和右边相邻牌上的数字。最后一次移动后，只剩下两张牌。

请计算可以得到的最小总得分。

输入格式

第一行包含一个整数 $n$，表示牌的数量。

第二行包含 $n$ 个整数，表示每张牌上的数字，相邻整数之间用一个空格分隔。

输出格式

输出一行一个整数，表示最小总得分。

6
10 1 50 50 20 5

3650

数据范围与提示

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