Головна і майже єдина відмінність задачі від попередньої задачі «Комп'ютерна гра (платформи)» – слід знайти відповідь не лише як число, а й як маршрут (послідовність платформ).

Водночас, тести інші (вхідні дані тестів з однаковими номерами в цих задачах, як правило, різні).

У старих іграх можна зіткнутися з такою ситуацією. Персонаж стрибає по платформах, які висять у повітрі. Він повинен перебратися від одного краю екрана до іншого. При стрибку з платформи на сусідню, персонаж витрачає ~|y_2 - y_1|~ енергії, де ~y_1~ і ~y_2~ — висоти, на яких розташовані ці платформи. Крім того, є суперприйом, що дозволяє перескочити через платформу, але на це витрачається ~3\cdot|y_3 - y_1|~ енергії.

Звісно ж, енергію потрібно витрачати максимально економно, а Суперприйом можна використовувати будь-яку кількість разів (зокрема й не використовувати взагалі).

Вам відомі координати усіх платформ у порядку від лівого краю до правого. Знайдіть мінімальну кількість енергії, потрібну персонажу, щоб дістатись від першої платформи до останньої, та шлях (маршрут), за яким можна дістатись від першої платформи до останньої, витративши цю кількість енегрії.

Вхідні дані

У першому рядку записана кількість платформ ~n~ (~2\leqslant n\leqslant 10^5~). Другий рядок містить ~n~ натуральних чисел, які не перевищують 4000 – висоти, на яких розміщено платформи.

Результати

У першому рядку виведіть єдине число – мінімальну кількість енергії, яку повинен витратити персонаж гри на подолання платформ.

У другому рядку виведіть єдине число – кількість платформ, через які проходить Ваш маршрут.

У третьому рядку виведіть через пробіли стільки чисел, скільки Ви вказали у другому рядку – послідовність платформ, належних Вашому маршруту.

Приклади

Вхід

4
1 2 3 30

Результат

29
4
1 2 3 4

Вхід

5
1 1 1 1 1

Результат

0
3
1 3 5

Вхід

10
1 100 1 100 1 100 1 100 1 100

Результат

99
6
1 2 4 6 8 10

Примітки

1. При ввиведенні маршруту, вважати, що платформи занумеровані від 1-ї до ~n~-ї.
2. В цьому завданні для деяких вхідних даних можливі різні правильні маршрути (якщо вони якраз дають однакову мінімальну кількість енергії). Ваша програма повинна виводити будь-який один з них; перевірка відбувається за смислом, а не зіставленням зі зразком-маршрутом. Власне, серед наведених трьох прикладів лише в першому є тільки одна правильна відповідь, а і в другому, і в третьому є й інші правильні маршрути з тією ж мінімальною кількістю енергії.