题目背景

个人的遭遇，命运的多舛都使我被迫成熟，这一切的代价都当是日后活下去的力量。 —— 三毛

小 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