Matrix Chain Multiplication

Hard#dynamic-programming #interval-dp· solved by 0 · time limit 2.0 s

Matrices $A_1 \dots A_n$ have sizes $d_0 \times d_1, d_1 \times d_2, \dots, d_{n-1} \times d_n$ . Multiplying a $p \times q$ by a $q \times r$ matrix costs $p \cdot q \cdot r$ . Find the minimum total cost to compute the whole product (choose the best bracketing).

Input

$n$ , then the $n+1$ dimensions $d_0 \dots d_n$ .

Output

The minimum cost.

Constraints

$1 \le n \le 200$ , $1 \le d_i \le 100$

Sample 1

Input

3
10 30 5 60

Output

Sample 2

Input

4
40 20 30 10 30

Output