Решение задачи "Минимальная триангуляция" с Codeforces

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

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