Вам задан правильный многоугольник из \(n\) вершин, пронумерованных от \(1\) до \(n\) против часовой стрелки. Триангуляция данного многоугольника — это набор треугольников такой, что каждая вершина любого из треугольников является вершиной первоначального многоугольника, не существует пары треугольников имеющих положительную площадь пересечения, и площадь объединения треугольников равна площади многоугольника. Вес триангуляции — это сумма весов треугольников из которых она состоит, где весом треугольника является произведение меток его вершин.
Найдите минимальный вес среди всех триангуляций заданного многоугольника.
Выходные данные
Выведите единственное число — минимальный вес среди всех триангуляций заданного многоугольника.
Примечание
Согласно Вики: триангуляция многоугольника — это декомпозиция простого многоугольника \(P\) на набор треугольников, другими словами, нахождение набора треугольников с попарно непересекающимися внутренними частями, объединение которых равно \(P\).
В первом примере многоугольник — это треугольник, поэтому его не надо делить дальше. Ответ, соответственно, равен \(1 \cdot 2 \cdot 3 = 6\).
Во втором примере многоугольник — это прямоугольник, его необходимо разбить на два треугольника. Выгодно разделить его используя диагональ \(1-3\), а потому ответ \(1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
6
|
|
2
|
4
|
18
|