A tensor pipeline multiplies a chain of n matrices together, in the fixed left-to-right order M1 * M2 * ... * Mn. The dimensions are given by an array p of n+1 integers, where matrix Mi has p[i-1] rows and p[i] columns (1-indexed), so consecutive matrices are conformable.
Multiplying an a x b matrix by a b x c matrix takes a * b * c scalar multiplications and yields an a x c matrix. Matrix multiplication is associative, so you may fully parenthesize the chain however you like; different parenthesizations need different numbers of scalar multiplications. Report the minimum total number of scalar multiplications needed to compute the whole product.
Input format
Line 1: an integer n, the number of matrices.
Line 2: n+1 space-separated positive integers, the dimension array p.
Output format
A single integer: the minimum number of scalar multiplications (0 when n is 1).
Constraints
- 1 <= n <= 100
- 1 <= each dimension <= 500