矩阵环相乘

题目描述

矩阵链相乘相信大家都会，不妨尝试一下矩阵环相乘。

$n$个矩阵围成一个环，求这$n$个矩阵需要的最少乘法次数。

输入

第一个数矩阵个数$n$

接下来$n$个数，表示每个矩阵的行数，显然，这些矩阵满足矩阵相乘的条件，所以第$i+1$个矩阵的行数等于第$i$个矩阵的列数，第$0$个矩阵的行数等于第$n-1$个矩阵的列数。

输出

一个整数，表示最少的乘法次数。

样例

输入:
3
3 2 2
输出:
20

样例解释

第$0$个矩阵为$3 \times 2$，第$1$个为$2 \times 2$，第$2$个为$2 \times 3$。
先将第$2$个与第$0$个相乘，共$2 \times 3 \times 2=12$次乘法，得到一个$2 \times 2$的矩阵，然后与第$1$个相乘，需要$2 \times 2 \times 2=8$次乘法，因此共$12+8=20$次乘法。

数据范围

$n \leq 300$