1. You are given an array(arr) of length N which represents N number of balloons. 2. Each balloon is painted with a number on it. 3. You have to collect maximum coins by bursting all the balloons. 4. If you burst a balloon with index i, you will get (arr[i-1] * arr[i] * arr[i+1]) number of coins. 5. If arr[i-1] and arr[i+1] don't exist, then you may assume their value as 1.
Input Format
A number N a1 a2.. N integers
Output Format
Check the sample output and question video.
Constraints
1 <= N <= 1000 1 <= arr[i] <= 100
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
3 1 2 3
Output
12