//Count the minimum number of jumps required for a frog to get to the other side of a river.

import java.util.*;

//TODO better Performance and Correctness
class Solution {
    public int solution(int[] A) {

        int position = -1;
        int end = A.length;
        int jumps = 0;
        int jumpsFW = Integer.MAX_VALUE;
        int jumpsBW = Integer.MAX_VALUE;

        ArrayList<Integer> fibs = new ArrayList<Integer>();
        int n = 1;
        int fib = 0;
        do{
            fib = fibonacci(n);
            fibs.add(fib);
            n++;
        }while(fib < end + 1);

        final int[] fibArray = fibs.stream().distinct()
                                      .filter(num -> num <= A.length  + 1)
                                      .mapToInt(Integer::intValue)
                                      .toArray();

        for(int i = fibArray.length - 1; i >= 0; i--){

            //Try to jump to Finish
            if(position + fibArray[i] == end){
                jumps++;
                jumpsFW = jumps;
                break;
            //It's not allowed to jump beyond the end
            }else if(position + fibArray[i] > end){
                continue;
            //Try to jump as far as possible
            }else{
                    if(A[position + fibArray[i]] == 1){
                        //System.out.println(position + fibArray[i]);
                        position = position + fibArray[i];
                        i = fibArray.length - 1;
                        jumps++;
                    }
            }
        }

        //Backwards
        int start = -1;
        position = A.length;
        jumps = 0;

        for(int i = fibArray.length - 1; i >= 0; i--){

            //Try to jump to the Start
            if(position - fibArray[i] == start){
                jumps++;
                jumpsBW = jumps;
                break;
            //It's not allowed to jump beyond the start
            }else if(position - fibArray[i] < start){
                continue;
            //Try to jump as far as possible
            }else{
                    if(A[position - fibArray[i]] == 1){
                        //System.out.println(position - fibArray[i]);
                        position = position - fibArray[i];
                        i = fibArray.length - 1;
                        jumps++;
                    }
            }
        }

        jumps = jumpsFW < jumpsBW           ? jumpsFW : jumpsBW;
        jumps = jumps   < Integer.MAX_VALUE ? jumps   : -1;

        return jumps;
    }

    public int fibonacci(int n){

        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else{
            return fibonacci(n-2) + fibonacci(n-1);
        }

    }
}