Matrix Chain Multiplication

Given n matrices, where the dimensions of the i-th matrix M_i are \(w_i \times w_{i+1}\) (we do not care about the elements of the matrices), we wish to compute the chain product

\[ M = M_1 \times M_2 \times \cdots \times M_n \]

Matrix multiplication is not commutative but is associative. Thus, by arranging the order of multiplications appropriately, the total number of scalar multiplications can be minimized. In this problem, multiplying a matrix of size \(a \times b\) with a matrix of size \(b \times c\) is defined to cost \(abc\) operations.

Your task is to calculate the minimum number of operations needed to compute the chain product of the given n matrices. You do not need to output the actual multiplication order.

inputFormat

The input consists of two lines:

• The first line contains an integer n (the number of matrices).
• The second line contains n+1 integers \(w_1, w_2, \ldots, w_{n+1}\), where the i-th matrix has dimensions \(w_i \times w_{i+1}\).

outputFormat

Output a single integer representing the minimum number of scalar multiplications required to compute the product of the matrices.

sample

3
2 3 4 5

64