[EER1] 代价

> 个人的遭遇，命运的多舛都使我被迫成熟，这一切的代价都当是日后活下去的力量。 —— 三毛 小 Z 喜欢玩数字游戏。

给出一个长度为 $n+2$ 的序列 $a_i$，其中第 $1$ 个数和第 $n+2$ 个数固定为 $1$。你每次可以选择序列中间的一个数删除（不能是第一个和最后一个），删除位置 $p$ 上的数的代价为 $a_{p-1} \times a_p \times a_{p+1}$。你需要执行这个操作直到无法操作为止。求最小的代价和。

第一行一个正整数 $n$。 第二行 $n$ 个正整数，第 $i$ 个数表示 $a_{i+1}$。

一行一个正整数，表示最小的代价和。

3
1 2 3

9

4
19 26 8 17

846

6
1 1 1 1 1 1

6

样例一解释： 先删除 $3$，代价为 $6$，再删除 $2$，代价为 $2$，再删除 $1$，代价为 $1$。 总代价为 $6+2+1=9$。 --- **本题采用捆绑测试。** 对于 $100\%$ 的测试点：$1 \leq n \leq 10^6$，$1 \leq a_i \leq 10^4$。 本题共 $6$ 个子任务，各子任务的分值及约定如下： 子任务 $1$（$1$ 分）：$a_i = 1$。 子任务 $2$（$14$ 分）：$1 \leq n \leq 10$。 子任务 $3$（$5$ 分）：$1 \leq a_i \leq 2$。 子任务 $4$（$14$ 分）：$1 \leq n \leq 40$。 子任务 $5$（$26$ 分）：$1 \leq n \leq 500$。 子任务 $6$（$40$ 分）：无特殊限制。 #### 特别感谢 idea：smrsky solu：CYJian data：iostream