Числа#1762
Дано послідовність цілих чисел a_1, a_2, \ldots, a_n. За одну операцію ви можете видалити будь-який елемент (крім першого й останнього), сплативши штраф, який дорівнює добутку цього елемента на суму його сусідів. Ваше завдання — видалити всі елементи, крім першого й останнього, з мінімально можливим сумарним штрафом.
Наприклад, розглянемо послідовність:
1 50 51 50 1
Видаляємо четвертий елемент: штраф дорівнює 50 \times (1 + 51) = 2600, у результаті отримаємо:
1 50 51 1
Видаляємо третій елемент: штраф дорівнює 51 \times (50 + 1) = 2601, у результаті отримаємо:
1 50 1
Видаляємо другий елемент: штраф дорівнює 50 \times (1 + 1) = 100.
Сумарний штраф — .
У першому рядку знаходиться одне ціле число (1 \leq n \leq 100) — кількість елементів у послідовності.
У другому рядку задано цілих чисел a_1, a_2, \ldots, a_n (|a_i| \leq 100).
Виведіть одне число — мінімальний можливий сумарний штраф.
Приклад 1