D. Коровки и классные последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бесси с коровками недавно играли с «классными» последовательностями и пытались построить некоторые из них. К сожалению, они плохо считают, так что им нужна Ваша помощь!

Пара положительных целых чисел (x, y) называется «классной», если x можно представить как сумму y последовательных целых чисел (не обязательно положительных). Последовательность (a1, a2, ..., an) называется «классной», если пары (a1, a2), (a2, a3), ..., (an - 1, an) все являются классными.

У коровок есть последовательность из n положительных целых чисел, a1, a2, ..., an. За один ход можно заменить некоторое ai любым другим положительным целым числом (других ограничений на новое значение ai нет). Определите наименьшее количество ходов, необходимое для того, чтобы итоговая последовательность стала «классной».

Входные данные

В первой строке записано единственное целое число n (2 ≤ n ≤ 5000). В следующей строке записаны через пробел n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1015).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

Выведите единственное целое число, минимальное количество ai, которое надо поменять, чтобы последовательность стала классной.

Примеры
Входные данные
3
6 4 1
Выходные данные
0
Входные данные
4
20 6 3 4
Выходные данные
2
Примечание

В первом примере последовательность уже «классная», так что никаких элементов менять не надо.

Во втором примере можно изменить a2 на 5, а a3 — на 10, чтобы получить (20, 5, 10, 4), являющуюся «классной». Итого, меняются 2 элемента.