eolymp
Змагання

Комбинаторика. Формула

Минимальная триангуляция

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

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

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

Одно целое число n (3n500) - количество вершин в правильном многоугольнике.

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
Вихідні дані #1
6
Вхідні дані #2
4
Вихідні дані #2
18