1. You are given an array of integers, which represents the vertices of an N-sided convex polygon in clockwise order. 2. You have to triangulate the given polygon into N-2 triangles. 3. The value of a triangle is the product of the labels of vertices of that triangle. 4. The total score of the triangulation is the sum of the value of all the triangles. 5. You have to find the minimum score of the triangulation of the given polygon.
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
6