Масив псують лише рівні сусіди, а кожна операція змінює елемент на . Тому жодному елементу ніколи не потрібно зсуватися більш ніж на одиницю: якщо його вже відсунули на два, його можна повернути на крок назад і він усе одно відрізнятиметься від того сусіда, від якого його відсували.
Отже кожна позиція має лише три кандидати — a_i - 1, a_i та a_i + 1 — і задача стає динамічним програмуванням уздовж масиву: — мінімальна кількість операцій на префіксі за умови, що на -й позиції стоїть -й кандидат. Перехід перебирає три кандидати попередньої позиції та відкидає ті, значення яких збігається з поточним:
Відповідь — мінімум по трьох станах останньої позиції. Зверніть увагу, що значення можуть виходити за межі [0, 10^9] (наприклад, масив [0,0,0,0] вигідно перетворити на [0,1,-1,0]), і це дозволено умовою.
Складність: з константою .
Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.