use std::collections::VecDeque;

fn fib_frog(a: &[i64]) -> i64 {
    let size = a.len() as i64;

    let mut fib = vec![0i64, 1];
    let mut i = 1;
    while fib[i] <= size {
        i += 1;
        fib.push(fib[i - 1] + fib[i - 2]);
    }

    let mut paths: VecDeque<(i64, i64)> = VecDeque::new();
    paths.push_back((-1, 0));

    let mut steps = vec![false; size as usize];

    while let Some((idx, jmp)) = paths.pop_front() {
        for f in (2..fib.len()).rev() {
            let next_idx = idx + fib[f];
            if next_idx == size {
                return jmp + 1;
            }
            if next_idx > size || steps[next_idx as usize] || a[next_idx as usize] == 0 {
                continue;
            }
            if a[next_idx as usize] == 1 {
                steps[next_idx as usize] = true;
                paths.push_back((next_idx, jmp + 1));
            }
        }
    }

    -1
}