Комп`ютерна гра з відновленням шляху
У багатьох старих іграх з двовимірною графікою можна зіткнутись з подібною ситуацією. Який небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається |y_2-y_1| енергії, де y_2 та y_1 - висоти, на яких розміщені ці платформи. Крім того у героя є суперприйом, який дозволяє перестрибнути через платформу, але на це витрачається 3·|y_2-y_1| одиниць енергії. Звичайно ж, енергію потрібно витрачати максимально економно.
Відомі висоти платформ у порядку від лівого краю до правого. Знайдіть мінімальну кількість енергії, достатню, щоб дістатись з 1-ї платформи до n-ї (останньої) та список (послідовність) платформ, по яким потрібно пройти.
Вхідні дані
Перший рядок містить кількість платформ N (2 ≤ N ≤ 100000), другий - N цілих чисел, значення яких не перевищують по модулю 4000 - висоти платформ.
Вихідні дані
У першому рядку виведіть мінімальну кількість енергії. У другому - кількість платформ, по яким потрібно пройти, а у третьому виведіть послідовність цих платформ.
Примітка
Зрозуміло, у цій задачі для деяких вхідних даних можливі різні правильні послідовності платформ. Ваша програма повинна виводити довільну з них.