Комп`ютерна гра - квадратичні стрибки
Ви можете згадати хоча б одного свого знайомого до двадцярічного віку, який у дитинстві не грав у комп'ютерні ігри? Якщо так, то можливо ви і самі не знайомі з цією розвагою? Втім труднощів при розв'язуванні цієї задачі це створтити не повинно.
У багатьох старих іграх з двовимірною графікою можна зіткнутись з подібною ситуацією. Який небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається |y_2-y_1|^2 енергії, де y_2 та y_1 - висоти, на яких розміщені ці платформи. Крім того у героя є суперприйом, який дозволяє перестрибнути через платформу, але на це витрачається 3·|y_2-y_1|^2 одиниць енергії. Звичайно ж, енергію потрібно витрачати максимально економно.
Припустимо, що вам відомі координати усіх платформ у порядку від лівого краю до правого. Чи зможете ви знайти, яку мінімальну кількість енергії потрібно герою, щоб дістатись від першої платформи до останньої?
Вхідні дані
У першому рядку записано кількість платформ n (2 ≤ n ≤ 100000). Другий рядок містить n натуральних чисел, які не перевищують 4000 - висоти, на яких розміщено платформи.
Вихідні дані
Виведіть єдине число - мінімальну кількість енергії, яку повинен витратити гравець на подолання платформ (звичайно ж у припущенні, що cheat-коди використовувати не можна).