Задача, прошу помочь.

[ronaldo007]

Дана последовательность чисел a1, a2, ..., an. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом.

Пример начальной последовательности:

1 50 51 50 1

удаляем четвертое число, штраф 50·(1 + 51) = 2600, получаем

1 50 51 1

удаляем третье число, штраф 51·(50 + 1) = 2601, получаем

1 50 1

удаляем второе число, штраф 50·(1 + 1) = 100.

Итого, штраф 5301.

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

В первой строке входного файла расположено одно число n (1 ≤ n ≤ 100) — количество чисел в последовательности.

Во второй строке находятся n целых чисел a1, a2, ... an; никакое из чисел по модулю не превосходит 100.

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

Выведите в выходной файл одно число — минимальный суммарный штраф.