#include <queue>
#include <vector>

int fibFrog(const std::vector<int>& a)
{
    int size = static_cast<int>(a.size());

    std::vector<int> fib{0, 1};
    for (int i = 1; fib[i] <= size;) {
        ++i;
        fib.push_back(fib[i - 1] + fib[i - 2]);
    }

    struct Path {
        int idx;
        int jmp;
    };

    std::queue<Path> paths;
    paths.push({-1, 0});

    std::vector<bool> steps(size, false);

    while (!paths.empty()) {
        Path path = paths.front();
        paths.pop();

        for (int i = static_cast<int>(fib.size()) - 1; i >= 2; --i) {
            int idx = path.idx + fib[i];
            if (idx == size) {
                return path.jmp + 1;
            }
            if (idx > size || steps[idx] || a[idx] == 0) {
                continue;
            }
            if (a[idx] == 1) {
                steps[idx] = true;
                paths.push({idx, path.jmp + 1});
            }
        }
    }

    return -1;
}