A signal-processing pipeline applies n matrix transforms in a fixed order: transform 1 is applied, then transform 2, and so on through transform n, which is equivalent to computing the matrix product M1 x M2 x ... x Mn. Matrix Mi has dimensions p[i-1] by p[i] (rows by columns). Multiplying an a x b matrix by a b x c matrix costs exactly a * b * c scalar multiplications and produces an a x c matrix. Matrix multiplication is associative, so the product can be computed in different orders (different parenthesizations) that may have very different total costs. Find the minimum total number of scalar multiplications needed to compute the full product, choosing the parenthesization freely.
Input format
Line 1: an integer n (the number of matrices).
Line 2: n + 1 space-separated integers p[0] p[1] ... p[n], the chain of dimensions.
Output format
A single integer: the minimum total number of scalar multiplications needed to compute M1 x M2 x ... x Mn. If n == 1, print 0 (no multiplication is needed).
Constraints
- 1 <= n <= 8
- 1 <= p[i] <= 50