e-olymp
Змагання

Azerbaijan Programming Olympiad - 2nd Stage preparation

Платформи - 3

У старих іграх можна зустрітися з такою ситуацією. Герой стрибає по платформах, які висять в повітрі. Він повинен перебратися з одного краю екрану до іншого. Під час стрибка з платформи на сусідню, герой витрачає |y2 - y1|^2 енергії, де y1 і y2 - висоти, на яких розміщені ці платформи. Крім того, є суперприйом, що дозволяє перестрибнути через платформу, але на це витрачається 3 * |y3 - y1|^2 енергії. Через ^ тут позначається піднесення до степені.

Відомі висоти платформи в порядку від лівого краю до правого. Знайдіть мінимальну кількість енергії, яку потрібно, щоб добратися з 1-й платформи до n-й (останньої).

Вхідні дані

Перший рядок містить кількість платформ n (2n100000), другий - n цілих чисел, значення яких не перквищує за модулем 4000 - висоти платформ.

Вихідні дані

Виведіть єдине ціле число - знайдена кількість енергії.

Ліміт часу 1 секунда
Ліміт використання пам'яті 122.49 MiB
Вхідні дані #1
4
1 2 3 30
Вихідні дані #1
731