e-olymp
Змагання

Dynamic Programming - Linear

Платформи

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

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

Вхідні дані

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

Вихідні дані

В першому рядку виведіть минимальну кількість енергії. У другому - кількість платформ, по яким потрібно пройти, а в третьому виведіть список цих платформ.

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