from collections import deque


def fib_frog(a: list[int]) -> int:
    size = len(a)

    fib = [0, 1]
    i = 1
    while fib[i] <= size:
        i += 1
        fib.append(fib[i - 1] + fib[i - 2])

    queue = deque([(-1, 0)])
    visited = [False] * size

    while queue:
        idx, jumps = queue.popleft()
        for f in range(len(fib) - 1, 1, -1):
            new_idx = idx + fib[f]
            if new_idx == size:
                return jumps + 1
            if new_idx > size or visited[new_idx] or a[new_idx] == 0:
                continue
            if a[new_idx] == 1:
                visited[new_idx] = True
                queue.append((new_idx, jumps + 1))

    return -1

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
}

function fibFrog(a: number[]): number {
  const size = a.length;

  const fib: number[] = [0, 1];
  for (let i = 1; fib[i] <= size; ) {
    i++;
    fib[i] = fib[i - 1] + fib[i - 2];
  }

  type Path = { idx: number; jmp: number };
  const paths: Path[] = [{ idx: -1, jmp: 0 }];
  const steps: boolean[] = new Array(size).fill(false);

  while (paths.length > 0) {
    const path = paths.shift() as Path;
    for (let i = fib.length - 1; i >= 2; i--) {
      const 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, jmp: path.jmp + 1 });
      }
    }
  }

  return -1;
}

fish() {
    local -n _a="$1"
    local -n _b="$2"
    local _size=${#_a[@]}
    local _dead=0
    local -a _stack=()
    local _i
    for ((_i = 0; _i < _size; _i++)); do
        if (( _b[_i] == 1 )); then
            _stack+=("${_a[_i]}")
        elif (( ${#_stack[@]} > 0 )); then
            while (( ${#_stack[@]} > 0 )); do
                ((_dead++))
                local _top=${_stack[-1]}
                if (( _a[_i] > _top )); then
                    unset '_stack[-1]'
                    _stack=("${_stack[@]}")
                else
                    break
                fi
            done
        fi
    done
    echo $(( _size - _dead ))
}

#include <vector>

int fish(const std::vector<int>& a, const std::vector<int>& b)
{
    int size = static_cast<int>(a.size());
    int dead = 0;
    std::vector<int> downstream;

    for (int i = 0; i < size; ++i) {
        if (b[i] == 1) {
            downstream.push_back(a[i]);
        } else if (!downstream.empty()) {
            while (!downstream.empty()) {
                ++dead;
                if (a[i] > downstream.back()) {
                    downstream.pop_back();
                } else {
                    break;
                }
            }
        }
    }

    return size - dead;
}

static int Fish(int[] a, int[] b)
{
    var size = a.Length;
    var dead = 0;
    var fish = new Stack<int>();

    for (int i = 0; i < size; i++)
    {
        if (b[i] == 1)
        {
            fish.Push(a[i]);
        }
        else
        {
            while (fish.Count > 0)
            {
                dead++;
                if (a[i] > fish.Peek())
                {
                    fish.Pop();
                }
                else
                {
                    break;
                }
            }
        }
    }

    return size - dead;
}

defmodule Fish do
  def fish(a, b) do
    size = length(a)

    {_stack, dead} =
      a
      |> Enum.zip(b)
      |> Enum.reduce({[], 0}, fn {size_i, dir_i}, {stack, dead} ->
        if dir_i == 1 do
          {[size_i | stack], dead}
        else
          fight(size_i, stack, dead)
        end
      end)

    size - dead
  end

  defp fight(_size_i, [], dead), do: {[], dead}

  defp fight(size_i, [top | rest] = stack, dead) do
    if size_i > top do
      fight(size_i, rest, dead + 1)
    else
      {stack, dead + 1}
    end
  end
end

-module(fish).
-export([fish/2]).

fish(A, B) ->
    Pairs = lists:zip(A, B),
    {_, Dead} = lists:foldl(fun({Ai, Bi}, {Stack, D}) ->
        case Bi of
            1 -> {[Ai | Stack], D};
            _ -> fight(Ai, Stack, D)
        end
    end, {[], 0}, Pairs),
    length(A) - Dead.

fight(_Ai, [], Dead) ->
    {[], Dead};
fight(Ai, [Top | Rest], Dead) ->
    Dead1 = Dead + 1,
    case Ai > Top of
        true -> fight(Ai, Rest, Dead1);
        false -> {[Top | Rest], Dead1}
    end.

func fish(a, b []int) int {
	size := len(a)
	dead := 0
	downstream := make([]int, 0, size)

	for i := 0; i < size; i++ {
		if b[i] == 1 {
			downstream = append(downstream, a[i])
		} else {
			for len(downstream) > 0 {
				dead++
				if a[i] > downstream[len(downstream)-1] {
					downstream = downstream[:len(downstream)-1]
				} else {
					break
				}
			}
		}
	}

	return size - dead
}

fish :: [Int] -> [Int] -> Int
fish a b = size - dead
  where
    size      = length a
    (dead, _) = foldl step (0, []) (zip a b)

    step (d, stack) (ai, bi)
      | bi == 1   = (d, ai : stack)
      | otherwise = fight ai stack d

    fight _  []             d = (d, [])
    fight ai (top : tops) d
      | ai > top  = fight ai tops (d + 1)
      | otherwise = (d + 1, top : tops)