1195. Minimum Score Triangulation of Polygon

Given the vertex values of a convex polygon in order, triangulating it into triangles gives each triangle a score equal to the product of its three vertex values. Return the minimum total score over all triangulations. The input is JSON {values}.

Input: JSON {values}.

Output: Integer — the minimum triangulation score.

Examples

Input: {"values":[1,2,3]}
Output: 6
Explanation: One triangle: 1*2*3.

Input: {"values":[3,7,4,5]}
Output: 144
Explanation: Best triangulation scores 144.

Input: {"values":[1,3,1,4,1,5]}
Output: 13
Explanation: Optimal triangulation.

Constraints

• 3<=n<=50

Asked by