Задача Platforms
В старих іграх можна зустрітись з такою ситуацією. Герой стрибає по платформах, що висять у повітрі. Він повинен перебратися від одного краю екрана до іншого. В одній з версій даної гри, при стрибку з платформи на сусідню, у героя витрачається |y2–y1| енергії, де y1 і y2 — висоти, на яких розміщено ці платформи. Крім того, є суперприйом, що дозволяє перескочити через платформу, але на це витрачається 3×|y3–y1| енергії. Інша версія відрізняється лише тим, що в функціях витрат енергії модулі замінено на квадрати, тобто. (y2–y1)2 при стрибку на сусідню та 3×(y3–y1)2 при стрибку через одну. Відомі висоти платформ у порядку від лівого краю до правого. Знайдіть (для кожної з версій гри) мінімальну кількість енергії, достатню, щоб дістатись з 1-ї платформи до n-ї (останньої).
Технічні умови: Програма повинна прочитати з клавіатури спочатку кількість платформ N (2≤N≤50000), потім N чисел в діапазоні від –2000 до +2000 кожне — висоти цих платформ. Програма повинна вивести на екран у єдиному рядку два розділені пропуском цілі числа — мінімальні необхідні затрати енергії для першої версії гри та для другої версії гри.
Приклад:
Введення: 3 0 20 11
Виведення: 29 363