Задачі
Комп`ютерна гра з відновленням шляху
Комп`ютерна гра з відновленням шляху
У багатьох старих іграх з двовимірною графікою можна зіткнутись з подібною ситуацією. Який небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається \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
У першому рядку виведіть мінімальну кількість енергії. У другому - кількість платформ, по яким потрібно пройти, а у третьому виведіть послідовність цих платформ.
\textbf{Примітка}
Зрозуміло, у цій задачі для деяких вхідних даних можливі різні правильні послідовності платформ. Ваша програма повинна виводити довільну з них.
Вхідні дані #1
4 1 2 3 30
Вихідні дані #1
29 4 1 2 3 4