e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

Платформи

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

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

Вхідні дані

Первая строка содержит количество платформ n (2n100000), вторая n целых чисел, значения которых не превышают по модулю 400 - высоты платформ.

Вихідні дані

В первой строке выведите минимальное количество энергии. Во второй - количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.

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