D. Минимальная триангуляция
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан правильный многоугольник из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$ против часовой стрелки. Триангуляция данного многоугольника — это набор треугольников такой, что каждая вершина любого из треугольников является вершиной первоначального многоугольника, не существует пары треугольников имеющих положительную площадь пересечения, и площадь объединения треугольников равна площади многоугольника. Вес триангуляции — это сумма весов треугольников из которых она состоит, где весом треугольника является произведение меток его вершин.

Найдите минимальный вес среди всех триангуляций заданного многоугольника.

Входные данные

Первая строка содержит единственное целое число $$$n$$$ ($$$3 \le n \le 500$$$) — количество вершин в правильном многоугольнике.

Выходные данные

Выведите единственное число — минимальный вес среди всех триангуляций заданного многоугольника.

Примеры
Входные данные
3
Выходные данные
6
Входные данные
4
Выходные данные
18
Примечание

Согласно Вики: триангуляция многоугольника — это декомпозиция простого многоугольника $$$P$$$ на набор треугольников, другими словами, нахождение набора треугольников с попарно непересекающимися внутренними частями, объединение которых равно $$$P$$$.

В первом примере многоугольник — это треугольник, поэтому его не надо делить дальше. Ответ, соответственно, равен $$$1 \cdot 2 \cdot 3 = 6$$$.

Во втором примере многоугольник — это прямоугольник, его необходимо разбить на два треугольника. Выгодно разделить его используя диагональ $$$1-3$$$, а потому ответ $$$1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18$$$.