Платформи
Платформи
У старих іграх можна зіткнутися з такою ситуацією. Герой стрибає по платформам, що висять у повітрі. Він має перебратися з одного краю екрана до іншого. При стрибку з платформи на сусідню, героя втрачає |y_2 - y_1| енергії, де y_1 і y_2 — висоти, на яких розміщені ці платформи. Крім того, є суперприйом, який дозволяє перестрибнути через платформу, але на цето затрачається 3 \cdot |y_3 - y_1| енергії.
Відомі висоти платформ у порядку з лввого краю до правого. Найдите мінимальну кількість енергиї, якої вистачить, щоб дістатись з 1-ї платформи на n-у (останню) і список (послідовність) платформ, по яким потрібно пройти.
Вхідні дані
Перший рядок містить кількість платформ n~(2 \le n \le 10^5), другий n цілих чисел, значення яких не превищують за модулем 4000 — висоти платформ.
Вихідні дані
В першому рядку виведіть минимальну кількість енергії. У другому — кількість платформ, по яким потрібно пройти, а в третьому виведіть список цих платформ.
Приклад
4 1 2 3 30
29 4 1 2 3 4
6 4 6 15 5 10 12
12 5 1 2 4 5 6