Cows and Cool Sequences

2000ms

262144K

Description:

Bessie and the cows have recently been playing with "cool" sequences and are trying to construct some. Unfortunately they are bad at arithmetic, so they need your help!

A pair (x, y) of positive integers is "cool" if x can be expressed as the sum of y consecutive integers (not necessarily positive). A sequence (a₁, a₂, ..., a_n) is "cool" if the pairs (a₁, a₂), (a₂, a₃), ..., (a_n - 1, a_n) are all cool.

The cows have a sequence of n positive integers, a₁, a₂, ..., a_n. In one move, they may replace some a_i with any other positive integer (there are no other limits on the new value of a_i). Determine the smallest number of moves needed to make the resulting sequence cool.

Input:

The first line contains a single integer, n (2 ≤ n ≤ 5000). The next line contains n space-separated integers, a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10¹⁵).

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output:

A single integer, the minimum number of a_i that must be changed to make the sequence cool.

Sample Input:

3
6 4 1

Sample Output:

Sample Input:

4
20 6 3 4

Sample Output:

Note:

In the first sample, the sequence is already cool, so we don't need to change any elements. In the second sample, we can change a₂ to 5 and a₃ to 10 to make (20, 5, 10, 4) which is cool. This changes 2 elements.

Informação

Provedor Codeforces

Código CF283D