e-olymp
Соревнования

January 19,20. One-dimentional Dynamic Programming

Платформы

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

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

Входные данные

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

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
4
1 2 3 30
Выходные данные #1
29
4
1 2 3 4