Платформы
Платформы
В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит |y[2] - y[1]| энергии, где y[1] и y[2] - высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается 3 * |y[3] - y[1]| энергии.
Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с 1-ой платформы до n-ой (последней) и список (последовательность) платформ, по которым нужно пройти.
Входные данные
Первая строка содержит количество платформ n (2 ≤ n ≤ 100000), вторая n целых чисел, значения которых не превышают по модулю 4000 - высоты платформ.
Выходные данные
В первой строке выведите минимальное количество энергии. Во второй - количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.
Пример
4 1 2 3 30
29 4 1 2 3 4
5 4000 -4000 4000 -4000 4000
0 3 1 3 5