CF1140D.Minimum Triangulation

You are given a regular polygon with $n$ vertices labeled from $1$ to $n$ in counter-clockwise order. The triangulation of a given polygon is a set of triangles such that each vertex of each triangle is a vertex of the initial polygon, there is no pair of triangles such that their intersection has non-zero area, and the total area of all triangles is equal to the area of the given polygon. The weight of a triangulation is the sum of weigths of triangles it consists of, where the weight of a triagle is denoted as the product of labels of its vertices.

Calculate the minimum weight among all triangulations of the polygon.

给你一个正 $n$ 边形，其顶点按逆时针顺序标记为 $1$ 到 $n$。该多边形的一个三角剖分（triangulation）是指一组三角形，满足以下条件：每个三角形的顶点均为原多边形的顶点；任意两个三角形的交集面积为零（即内部不重叠）；所有三角形的总面积等于该多边形的面积。一个三角剖分的权重定义为其中所有三角形权重之和，而每个三角形的权重定义为其三个顶点标签的乘积。

请计算该多边形所有可能三角剖分中权重的最小值。

The first line contains single integer $n$ ($3 \le n \le 500$) — the number of vertices in the regular polygon.

第一行包含一个整数 $n$（$3 \le n \le 500$）——正多边形的顶点数。

Print one integer — the minimum weight among all triangulations of the given polygon.

输出一个整数——给定多边形所有三角剖分中的最小权重。

According to Wiki: polygon triangulation is the decomposition of a polygonal area (simple polygon) $P$ into a set of triangles, i. e., finding a set of triangles with pairwise non-intersecting interiors whose union is $P$.

In the first example the polygon is a triangle, so we don't need to cut it further, so the answer is $1 \cdot 2 \cdot 3 = 6$.

In the second example the polygon is a rectangle, so it should be divided into two triangles. It's optimal to cut it using diagonal $1-3$ so answer is $1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18$.

根据维基百科：多边形三角剖分（polygon triangulation）是指将一个多边形区域（简单多边形）$P$ 分解为若干个三角形，即寻找一组内部两两不相交、且其并集恰好为 $P$ 的三角形。

在第一个例子中，该多边形本身就是一个三角形，因此无需进一步切割，答案为 $1 \cdot 2 \cdot 3 = 6$。

在第二个例子中，该多边形是一个矩形，因此应将其划分为两个三角形。最优的切割方式是沿对角线 $1$–$3$ 进行分割，故答案为 $1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18$。