Burst Balloons

You are given n balloons, each with a positive integer value. When you burst a balloon, you gain coins equal to the product of the values of the adjacent balloons. Formally, if you burst the balloon at index i (with value a_i), you will gain coins equal to
a[left] * a[i] * a[right], where a[left] and a[right] are the values of the adjacent balloons to the left and right of the burst balloon. If an adjacent balloon does not exist, consider its value as 1.

The task is to determine the maximum coins you can collect by bursting the balloons wisely until none remain.

More formally, let the input array be \(A = [a_1, a_2, \dots, a_n]\). By imagining two extra balloons with value 1 added on each end (i.e. \(A' = [1, a_1, a_2, \dots, a_n, 1]\)), the optimal strategy is to burst the internal balloons in an order that maximizes the total coins earned.

The recurrence relation for the dynamic programming solution is given by:

[ \text{dp}[l][r] = \max_{i \in (l, r)} \big( A'[l] \times A'[i] \times A'[r] + \text{dp}[l][i] + \text{dp}[i][r] \big) ]

Your goal is to compute \(\text{dp}[0][n+1]\) where \(n\) is the number of balloons in the original array.

inputFormat

The first line contains an integer n, the number of balloons.

The second line contains n space-separated integers representing the values of the balloons.

outputFormat

Output a single integer, the maximum coins that can be obtained by bursting the balloons in an optimal order.

## sample

4
3 1 5 8

167