Бесси с коровками недавно играли с «классными» последовательностями и пытались построить некоторые из них. К сожалению, они плохо считают, так что им нужна Ваша помощь!
Пара положительных целых чисел (x, y) называется «классной», если x можно представить как сумму y последовательных целых чисел (не обязательно положительных). Последовательность (a1, a2, ..., an) называется «классной», если пары (a1, a2), (a2, a3), ..., (an - 1, an) все являются классными.
У коровок есть последовательность из n положительных целых чисел, a1, a2, ..., an. За один ход можно заменить некоторое ai любым другим положительным целым числом (других ограничений на новое значение ai нет). Определите наименьшее количество ходов, необходимое для того, чтобы итоговая последовательность стала «классной».
Выходные данные
Выведите единственное целое число, минимальное количество ai, которое надо поменять, чтобы последовательность стала классной.
Примечание
В первом примере последовательность уже «классная», так что никаких элементов менять не надо.
Во втором примере можно изменить a2 на 5, а a3 — на 10, чтобы получить (20, 5, 10, 4), являющуюся «классной». Итого, меняются 2 элемента.