eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Платформи

Платформи

Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB

У старих іграх можна зіткнутися з такою ситуацією. Герой стрибає по платформам, що висять у повітрі. Він має перебратися з одного краю екрана до іншого. При стрибку з платформи на сусідню, героя втрачає |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 — висоти платформ.

Вихідні дані

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

Приклад

Вхідні дані #1
4
1 2 3 30
Вихідні дані #1
29
4
1 2 3 4
Вхідні дані #2
6
4 6 15 5 10 12
Вихідні дані #2
12
5
1 2 4 5 6