Задачи
Платформы
Платформы
В старых играх следующая ситуация встречается довольно часто. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с одной платформы на соседнюю, герой тратит $|y_2 - y_1|$ энергии, где $y_1$ и $y_2$ --- высоты соответствующих платформ. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3 \cdot |y_3 - y_1|$ единиц энергии.
Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-й платформы до $n$-й (последней), и список (последовательность) платформ, по которым нужно пройти.
\InputFile
Первая строка содержит количество платформ $n~(2 \le n \le 10^5)$. Вторая строка содержит $n$ целых чисел, значения которых не превышают по модулю $4000$ --- высоты платформ.
\OutputFile
В первой строке выведите минимальное количество энергии. Во второй строке выведите количество платформ, по которым нужно пройти. В третьей строке выведите список этих платформ.
\includegraphics{https://eolympusercontent.com/images/op6i6qnagd34h81m1q99cs2ffc.gif}
Входные данные #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