eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Платформы

Платформы

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

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

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

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

Первая строка содержит количество платформ n~(2 \le n \le 10^5). Вторая строка содержит n целых чисел, значения которых не превышают по модулю 4000 — высоты платформ.

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

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

Пример

Входные данные #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