Problem Description

Given $n$ matrices, the $i$-th matrix $M_i$ has size $w_i$ rows and $w_{i+1}$ columns, and we do not care about their contents. We consider multiplying them in order (called the chain product):

Matrix multiplication is not commutative, but it is associative. Therefore, by choosing a good order of association, we can reduce the number of operations as much as possible. In this problem, we define that multiplying a matrix of size $a \times b$ by a matrix of size $b \times c$ requires $abc$ operations.

Please compute the minimum number of operations needed to compute the chain product of the given $n$ matrices. For convenience, you do not need to construct the optimal order.

Input Format

The first line contains a positive integer $n$, representing the number of matrices.

The next line contains $n+1$ positive integers. The $i$-th integer is $w_i$, with the meaning described above.

Output Format

Output one integer, representing the minimum number of operations.

3
5 3 2 6

90

Hint

Sample explanation: The sample tells us that there are $n = 3$ matrices, with sizes $5 \times 3$, $3 \times 2$, and $2 \times 6$. Consider the two possible multiplication orders:

• Multiply $M_1$ and $M_2$ first to get a $5 \times 2$ matrix, then multiply it by $M_3$. The number of operations is $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$.
• Multiply $M_2$ and $M_3$ first to get a $3 \times 6$ matrix, then multiply it by $M_1$. The number of operations is $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

This problem asks for the minimum number of operations, so the answer is $90$.

Constraints: For all testdata, $1 \leq n \leq 2 \times 10^6$, $1 \leq w \leq 10^4$. Specifically:

• For $30\%$ of the testdata, $n \leq 500$.
• For another $30\%$ of the testdata, $n \leq 2 \times 10^5$.

Input Format

{{formatI}}

Output Format

{{formatO}}

Hint

{{hint}}

Translated by ChatGPT 5