抽卡片

题目描述

有 $N$ 张卡片摆成一行，每张卡片都包含一个正整数。在移动过程中，玩家从该行中取出一张卡片，得分等于所取卡片上的数字与其左右两侧卡片上数字的乘积。不允许取出该行中的第一张和最后一张卡片。最后一步之后，这一行只剩下两张卡片。

目标是按照一定的顺序抽取卡片，使总得分最少。

例如，如果行中的卡片包含数字 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$）。

第二行包含 1 到 100 之间的 $N$ 个整数，用空格分隔。

输出格式

输出必须包含一个整数，即最小分数。

样例输入 #1

6
10 1 50 50 20 5

样例输出 #1

3650

数据范围

$3 \le N \le 100$，每张卡片上的数字为 $1$ 到 $100$ 之间的整数。

知识点与难度

本题涉及的知识点从属于 GESP七级（区间DP），难度等级：⭐⭐⭐⭐⭐

测试点分布