Problem Statement

# Burst Balloons You are given `N` balloons in a row. Balloon `i` has the value `A[i]`. When you burst a remaining balloon with value `x`, you gain `left * x * right` coins, where `left` and `right` are the values of its nearest remaining neighbours. If there is no remaining neighbour on one side, use `1` on that side. Burst every balloon and print the maximum total number of coins you can collect. ## Input Format - The first line contains `N`. - The second line contains `N` space-separated integers `A[i]`. ## Output Format Print the maximum total number of coins. ## Constraints - `1 <= N <= 300` - `0 <= A[i] <= 100` - The answer fits in a signed 64-bit integer. ## Example 1 Input: 4 3 1 5 8 Output: 167 Explanation: One optimal order bursts values `1, 5, 3, 8`, earning `15 + 120 + 24 + 8 = 167` coins. ## Example 2 Input: 2 1 5 Output: 10 ## Notes - Neighbours are determined among balloons that have not yet been burst. - The virtual boundary values `1` are never burst. - Bal