Платформи#2688

Платформи

1 секунда

64 мегабайти

Легка

У класичних відеоіграх ви можете зіткнутися з ситуацією, коли герой стрибає по платформах, підвішених у повітрі, і йому потрібно дістатися з одного краю екрана на інший. В одній версії такої гри, коли герой стрибає з однієї платформи на сусідню, він витрачає $∣ y_{2} - y_{1} ∣$ |y_2 - y_1| енергії, де $y_{1}$ y_1 та $y_{2}$ y_2 — висоти цих платформ. Також є особливий стрибок, який дозволяє герою пропустити одну платформу, витрачаючи $3 \cdot ∣ y_{3} - y_{1} ∣$ 3 \cdot |y_3 - y_1| енергії. В іншій версії гри відмінністю є лише те, що у функціях витрат використовуються квадрати замість модулів: $(y_{2} - y_{1})^{2}$ (y_2 - y_1)^2 за стрибок на сусідню платформу і $3 \cdot (y_{3} - y_{1})^{2}$ 3 \cdot (y_3 - y_1)^2 за пропуск однієї. Висоти платформ подані у послідовності від крайньої лівої до крайньої правої. Для кожної версії гри визначте мінімальну кількість енергії, необхідну, щоб дістатися з $1$ -ї платформи на $n$ -ту (останню).

Вхідні дані

У першому рядку міститься число платформ $N$ ( $2 \leq N \leq 50000$ 2 \leq N \leq 50000), далі — $N$ цілих чисел у межах від $- 2000$ до $+ 2000$ , що задають висоти платформ.

Вихідні дані

Виведіть один рядок із двома цілими числами через пробіл — мінімальна кількість енергії для першої та другої версії гри відповідно.

Приклади

Приклад 1

Примітка

У першій версії вигідніше стрибати послідовно по платформах $0 \to 20 \to 11$ 0 \to 20 \to 11, витративши $20 + 9 = 29$ 20 + 9 = 29 енергії. У другій версії вигідніше стрибнути одразу з $0$ на $11$ ( $3 \cdot 1 1^{2} = 363$ 3 \cdot 11^2 = 363), ніж стрибати через усі платформи ( $2 0^{2} + 9^{2} = 481$ 20^2 + 9^2 = 481).