Ювелир работает с выпуклой пластиной в форме n-угольника. Вершины пластины занумерованы числами 0, 1, ..., n-1 по кругу, а каждой вершине i приписана ценность v_i.

Ювелир хочет разбить всю пластину на треугольные фрагменты, проводя непересекающиеся диагонали между вершинами. Любая полная триангуляция выпуклого n-угольника состоит ровно из n-2 треугольников.

Стоимость треугольного фрагмента с вершинами i, j, k равна произведению v_i * v_j * v_k.

Требуется определить минимальную возможную суммарную стоимость всех треугольников в такой триангуляции.

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

Первая строка содержит целое число n — количество вершин многоугольника.

Вторая строка содержит n целых чисел v_i — ценности вершин в порядке обхода по кругу.

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

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

Ограничения

• 3 <= n <= 300
• 1 <= v_i <= 100

Ответ может не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

3
1 2 3

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

6

Пример 2

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

4
1 100 1 100

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

200