# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def fib(N):
    F = [0, 1]
    while F[-1] < N:
        F.append(F[-1] + F[-2])
    return F

def solution(A):
    # write your code in Python 3.6
    F = fib(len(A)+1)
    steps = [-1] * (len(A) + 1)
    for f in F[1:]:
        if f - 1 == len(A) or f - 1 < len(A) and A[f-1] == 1:
            steps[f-1] = 1
    if steps[-1] != -1:
        return steps[-1]
    for i in range(0, len(A)):
        if steps[i] != -1:
            for f in F[2:]:
                if i + f > len(A): break
                if i + f == len(A) or A[i+f] == 1:
                    if steps[i+f] == -1:
                        steps[i+f] = steps[i] + 1
                    else:
                        steps[i+f] = min(steps[i+f], steps[i] + 1)
    return steps[-1]