import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {
    public static int fibFrog(int[] a) {
        int size = a.length;

        List<Integer> fib = new ArrayList<>(List.of(0, 1));
        for (int i = 1; fib.get(i) <= size; ) {
            i++;
            fib.add(fib.get(i - 1) + fib.get(i - 2));
        }

        Deque<int[]> paths = new ArrayDeque<>();
        paths.add(new int[]{-1, 0}); // {idx, jmp}

        boolean[] steps = new boolean[size];

        while (!paths.isEmpty()) {
            int[] path = paths.poll();
            int curIdx = path[0];
            int jmp = path[1];

            for (int i = fib.size() - 1; i >= 2; i--) {
                int idx = curIdx + fib.get(i);
                if (idx == size) {
                    return jmp + 1;
                }
                if (idx > size || steps[idx] || a[idx] == 0) {
                    continue;
                }
                if (a[idx] == 1) {
                    steps[idx] = true;
                    paths.add(new int[]{idx, jmp + 1});
                }
            }
        }

        return -1;
    }
}