Minimum Removal Cost

Given a sequence of length \( n+2 \) with fixed endpoints equal to 1, i.e., the sequence is \( [1, a_1, a_2, \dots, a_n, 1] \). You can repeatedly remove one of the interior elements (i.e. those at positions 2 to \( n+1 \)). When you remove an element at position \( p \), the cost incurred is \( a_{p-1} \times a_p \times a_{p+1} \). The removal process continues until only the two endpoints remain. Your task is to compute the minimum total cost required to remove all the interior elements.

Note: All formulas are represented in LaTeX format.

inputFormat

The first line contains an integer \( n \) (where \( n \ge 0 \)) representing the number of interior elements. The second line contains \( n \) space-separated integers: \( a_1, a_2, \dots, a_n \). The complete sequence becomes \( [1, a_1, a_2, \dots, a_n, 1] \).

outputFormat

Output a single integer representing the minimum total cost to remove all the interior elements.

sample

1
2

2