Числа
Задано послідовність чисел 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.
Вихідні дані
Виведіть одне число - мінімальний сумарний штраф.