Minimum triangulation

You are given a regular polygon with $n$ vertices numbered from $1$ to $n$ in counterclockwise order.

Triangulation of this polygon is a decomposition into triangles such that:

• each vertex of any triangle is a vertex of the original polygon;

• no two triangles have a positive-area intersection;

• the union of all triangles exactly covers the area of the original polygon.

The weight of a triangulation is defined as the sum of the weights of its triangles, where the weight of a triangle is the product of the labels of its vertices.

Find the minimum weight among all possible triangulations of the given polygon.

Examples

In the first test case, the polygon is a triangle with vertices $1,2,3$. Its weight is 1 \cdot 2 \cdot 3 = 6.

In the second test case, the polygon is a square with vertices 1, 2, 3, 4. The minimum weight is achieved by the triangulation with the diagonal $(1,3)$:

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18

Example 1

Loading

Loading

Example 2

Loading

Loading