# Minimum Score

Posted: 21 Mar, 2021

Difficulty: Moderate

#### 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.
```

##### Input Format:

```
The first line contains an integer ‘T’ which denotes the number of test cases.
The first line of each test case contains a single integer ‘N’, denoting the vertices of the polygon.
The next line contains ‘N’ space-separated integers denoting the value of the vertices of the polygon.
```

##### Output Format:

```
For each test case, you need to return the minimum triangle score possible from all triangles.
Print the output of each test case in a separate line.
```

##### Note:

```
You don’t need to print anything; It has already been taken care of. Just implement the given function.
```

##### 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
```