# 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