题目描述

有 $n$ 个矩阵，大小分别为：

a_0 \times a_1,
 a_1 \times a_2,
 a_2 \times a_3,
 \dots,
 a_{n-1} \times a_n

现在要将它们依次相乘，只能改变乘法的结合顺序，不能改变矩阵的相对顺序。请计算最少需要多少次运算。

两个大小分别为 $p \times q$ 和 $q \times r$ 的矩阵相乘时，运算次数计为 $p \times q \times r$。

输入格式

第一行输入一个整数 $n$，表示矩阵个数。

第二行输入 $n+1$ 个整数 $a_0,a_1,\dots,a_n$，表示矩阵大小。

输出格式

输出一个整数，表示最少的运算次数。

样例

3
1 10 5 20

150

数据范围

$1 \le n \le 1000$，$1 \le a_i \le 10000$。

来源

蓝桥杯练习系统