Дана последовательность чисел 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.

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

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