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

Вихідні дані

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