import Data.Array (Array, listArray, (!))
import qualified Data.Sequence as Seq
import Data.Sequence (Seq, ViewL (..), viewl, (|>))
import qualified Data.Set as Set

fibFrog :: [Int] -> Int
fibFrog a = go (Seq.singleton (-1, 0)) (Set.singleton (-1))
  where
    n = length a
    leaves = listArray (0, n - 1) a :: Array Int Int

    -- distinct Fibonacci jump lengths, up to the first one exceeding n
    jumps = takeWhile (<= n) fibJumps
      where
        fibJumps = 1 : 2 : zipWith (+) fibJumps (tail fibJumps)

    go :: Seq (Int, Int) -> Set.Set Int -> Int
    go queue visited = case viewl queue of
      EmptyL -> -1
      (pos, steps) :< rest
        | any (\j -> pos + j == n) jumps -> steps + 1
        | otherwise ->
            let (queue', visited') = foldl (enqueue pos steps) (rest, visited) jumps
            in  go queue' visited'

    enqueue pos steps (q, visited) j
      | idx >= 0 && idx < n && leaves ! idx == 1 && not (Set.member idx visited) =
          (q |> (idx, steps + 1), Set.insert idx visited)
      | otherwise = (q, visited)
      where
        idx = pos + j