Competitions

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

#### Input

One integer n (3n500) - the number of vertices in the regular polygon.

#### Output

Print the minimum weight among all triangulations of the given polygon.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3

Output example #1
6

Input example #2
4

Output example #2
18