# Minimum Score

Moderate
0/80
Average time to solve is 30m
Contributed by

## Problem statement

You are given an ‘N’ sided polygon. Every vertex of the polygon is assigned a value. The vertices are given in the form of an array of ‘N’ integers in clockwise direction.

You need to divide the polygon into ‘N - 2’ triangles. Each triangle has a triangle value. The triangle value is calculated by finding the product of its vertices.

Now, you need to find the minimum total triangle score. The total triangle score is the sum of the triangle scores of all the possible triangles.

Note:
``````Note that a polygon can be divided into triangles in more than one way. You need to print the minimum sum of triangle values of all the triangles created.
``````
Example :
``````Given 'N' = 4, Array = [4, 3, 5, 2], the possible scores for these two triangle score are: (3 * 2 * 5) + (3 * 2 * 4) = 54 and (4 * 2 * 5) + (4 * 3 * 5) = 100.
The minimum of these two triangle scores is 54. So you need to print 54.
``````

Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 10
3 <=  N  <= 50
1 <= ARR[i] <= 100

Where 'ARR[i]' denotes the Array elements that represent the sides of the polygon.

Time limit: 1 sec
``````
##### Sample Input 1:
``````2
4
4 3 5 2
3
4 5 6
``````
##### Sample Output 1:
``````54
120
``````
##### Explanation of Sample Output 1:
``````In the first test case,'N' = 4, 'ARR' = [4, 3, 5, 2]. The possible scores for these two triangle score are: (3 * 2 * 5) + (3 * 2 * 4) = 54 and (4 * 2 * 5) + (4 * 3 * 5) = 100. The minimum of these two triangle scores is 54. So you need to print 54.
``````

``````In test case 2, we know only 1 triangle is possible and hence its triangle score will be 120.
``````
##### Sample Input 2:
``````2
3
4 2 3
5
2 4 2 5 1
``````
##### Sample Output 2:
``````24
26
``````
##### Explanation of Sample Output 2:
``````In test case 1, Given 'N' = 3, 'ARR' = [4, 2, 3], the possible triangle score is: (4 * 2 * 3) = 24. So you need to print 24.
``````

``````In test case 2, Given 'N' = 5, 'ARR' = [2, 4, 2, 5, 1], the minimum of all the triangle scores is (1 * 2 * 4) + (1 * 4 * 2) + (1 * 2 * 5) = 26. So you need to print 26.
``````

Console