Minimum Score Of Triangulation
medium
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.
Constraints
1 <= N <= 1000 1 <= arr[i] <= 100
Format
Input
A number N a1 a2.. N integers
Output
Check the sample output and question video.
Example
Sample Input
3
1
2
3
Sample Output
6
Question Video