题目描述

小 $\verb!P!$ 得到了一个序列 $b$，其中有 $n$ 个元素，第 $i$ 个元素表示为 $b_i$。

定义一次操作为从序列中选出一个元素 $b_j$（$1 < j < n$），则该次操作得分为 $b_{j - 1} \times b_j \times b_{j + 1}$，且该序列的总得分为对该序列进行的所有操作的得分总和。

小 $\verb!P!$ 想进行若干次操作，直至序列中剩下首尾两个数为止，他希望序列的总得分最小，请你帮他找出最小总得分。

输入格式

第一行包含一个整数 $n$，表示序列的长度。

第二行包含 $n$ 个整数，表示序列 $b$。

输出格式

一行，一个整数，表示 $b$ 序列的最小总得分。

样例输入输出

5
10 1 50 20 5

1150

10
30 6 67 93 20 62 1 26 49 74

17033

说明/提示

【样例解释 #1】

其中包含一种最优方案为 $1150 = 1 \times 50 \times 20 + 1 \times 20 \times 5 + 10 \times 1 \times 5 = 1000 + 100 + 50$。

【数据范围】

对于 $100\%$ 的数据，满足 $1 \le n \le 500$，$1 \le b_i \le 10^3$。