Məsələlər
Компьютерная игра с восстановлением пути
Компьютерная игра с восстановлением пути
В старых играх можно столкнуться с подобной ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться с одного края экрана до другого. При прыжке с одной платформы на соседнюю, у героя уходит \textbf{|y_2-y_1|} энергии, где \textbf{y_2} и \textbf{y_1} - высоты, на которых расположены эти платформы. Кроме того у героя есть суперприём, который позволяет перескочить через платформу, но на это затрачивается \textbf{3*|y_2-y_1|} единиц энергии. Конечно же, энергию следует расходовать максимально экономно.
Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с \textbf{1}-й платформы до \textbf{n}-й (последней) и список (последовательность) платформ, по которым нужно пройти.
\InputFile
Первая строка содержит количество платформ \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{100000}), вторая - \textbf{N} целых чисел, значения которых не превышают по модулю \textbf{4000} - высоты платформ.
\OutputFile
В первой строке выведите минимальное количество энергии. Во второй - количество платформ, по которым нужно пройти, а в третьей выведите последовательность этих платформ.
\Note
Разумеется, в этой задаче для некоторых входных данных возможны разные правильные последовательности платформ. Ваша программа должна выводить любую из них.
Giriş verilənləri #1
4 1 2 3 30
Çıxış verilənləri #1
29 4 1 2 3 4