Числа
Дана последовательность чисел a[1], a[2], ..., a[n]. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом.
Например, пусть дана начальная последовательность:
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целых чисел a[1], a[2], ..., a[n], никакое из чисел не превосходит по модулю 100.
Выходные данные
Выведите одно число - минимальный суммарный штраф.