Burst Balloons to Maximize Coins

You are given a series of balloons, each with a positive integer score. When you burst a balloon, the coins you earn are equal to the product of the score of the balloon and the scores of its adjacent balloons. After bursting a balloon, its adjacent balloons become neighbors. Note that you may consider adding a balloon with value \(1\) at both ends of the array to simplify the calculation.

Your task is to determine the maximum number of coins you can collect by bursting the balloons in an optimal order.

The coin gain when bursting a balloon at index \(i\) is given by:

[ coins = nums[i-1] \times nums[i] \times nums[i+1] ]

where nums is the augmented array with \(1\) appended at both ends.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains a single integer \(n\) representing the number of balloons.
• If \(n > 0\), the second line contains \(n\) space-separated integers representing the scores of the balloons.
• If \(n = 0\), then no second line is provided.

outputFormat

Output a single integer to standard output (stdout) which is the maximum coins that can be collected by bursting all the balloons in an optimal order.

## sample

4
3 1 5 8

167

</p>