import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public static int fish(int[] a, int[] b) {
        int size = a.length;
        int dead = 0;
        Deque<Integer> fish = new ArrayDeque<>();

        for (int i = 0; i < size; i++) {
            if (b[i] == 1) {
                fish.push(a[i]);
            } else if (!fish.isEmpty()) {
                while (!fish.isEmpty()) {
                    dead++;
                    if (a[i] > fish.peek()) {
                        fish.pop();
                    } else {
                        break;
                    }
                }
            }
        }

        return size - dead;
    }
}

(defun fish (a b)
  (let* ((veca (coerce a 'vector))
         (vecb (coerce b 'vector))
         (size (length veca))
         (dead 0)
         (stack '()))
    (dotimes (i size)
      (if (= (aref vecb i) 1)
          (push (aref veca i) stack)
          (when stack
            (loop while stack
                  do (progn
                       (incf dead)
                       (if (> (aref veca i) (first stack))
                           (pop stack)
                           (return)))))))
    (- size dead)))

function fish(array $a, array $b): int
{
    $size  = count($a);
    $dead = 0;
    $fish  = [];
    for ($i = 0; $i < $size; $i++) {
        if ($b[$i] === 1) {
            $fish[] = $a[$i];
        } elseif (isset($fish[0])) {
            while (isset($fish[0])) {
                $dead++;
                if ($a[$i] > end($fish)) {
                    array_pop($fish);
                } else {
                    break;
                }
            }
        }
    }

    return $size - $dead;
}

def fish(a: list[int], b: list[int]) -> int:
    size = len(a)
    dead = 0
    downstream: list[int] = []

    for i in range(size):
        if b[i] == 1:
            downstream.append(a[i])
        else:
            while downstream:
                dead += 1
                if a[i] > downstream[-1]:
                    downstream.pop()
                else:
                    break

    return size - dead

fn fish(a: &[i64], b: &[i64]) -> i64 {
    let size = a.len();
    let mut dead = 0i64;
    let mut fish: Vec<i64> = Vec::new();

    for i in 0..size {
        if b[i] == 1 {
            fish.push(a[i]);
        } else if !fish.is_empty() {
            while let Some(&last) = fish.last() {
                dead += 1;
                if a[i] > last {
                    fish.pop();
                } else {
                    break;
                }
            }
        }
    }

    size as i64 - dead
}

function fish(a: number[], b: number[]): number {
  const size = a.length;
  let dead = 0;
  const downstream: number[] = [];

  for (let i = 0; i < size; i++) {
    if (b[i] === 1) {
      downstream.push(a[i]);
    } else if (downstream.length > 0) {
      while (downstream.length > 0) {
        dead++;
        if (a[i] > downstream[downstream.length - 1]) {
          downstream.pop();
        } else {
          break;
        }
      }
    }
  }

  return size - dead;
}

flags() {
    local -n _a="$1"
    local _size=${#_a[@]}
    local -a _peak _nxt
    _peak[0]=0
    local _i
    for ((_i = 1; _i < _size; _i++)); do
        local _right=0
        (( _i + 1 < _size )) && _right=${_a[_i+1]}
        if (( _a[_i-1] < _a[_i] && _a[_i] > _right )); then _peak[_i]=1; else _peak[_i]=0; fi
    done
    _nxt[_size-1]=-1
    for ((_i = _size - 2; _i >= 0; _i--)); do
        if (( _peak[_i] )); then _nxt[_i]=$_i; else _nxt[_i]=${_nxt[_i+1]}; fi
    done
    _i=1
    local _result=0
    while (( _i * (_i - 1) <= _size )); do
        local _pos=0 _num=0
        while (( _pos < _size && _num < _i )); do
            _pos=${_nxt[_pos]}
            if (( _pos == -1 )); then break; fi
            ((_num++))
            _pos=$(( _pos + _i ))
        done
        ((_i++))
        (( _num > _result )) && _result=$_num
    done
    echo "$_result"
}

#include <algorithm>
#include <vector>

int flags(const std::vector<int>& a)
{
    int size = static_cast<int>(a.size());
    if (size == 0) {
        return 0;
    }

    std::vector<bool> peaks(size, false);
    for (int i = 1; i < size; ++i) {
        int nextVal = (i + 1 < size) ? a[i + 1] : 0;
        peaks[i] = a[i - 1] < a[i] && a[i] > nextVal;
    }

    std::vector<int> next(size);
    next[size - 1] = -1;
    for (int i = size - 2; i >= 0; --i) {
        next[i] = peaks[i] ? i : next[i + 1];
    }

    int i = 1;
    int result = 0;
    while (i * (i - 1) <= size) {
        int pos = 0;
        int num = 0;
        while (pos < size && num < i) {
            pos = next[pos];
            if (pos == -1) {
                break;
            }
            ++num;
            pos += i;
        }
        ++i;
        result = std::max(result, num);
    }

    return result;
}

static int Flags(int[] a)
{
    var size = a.Length;
    if (size == 0)
    {
        return 0;
    }

    var peaks = new bool[size];
    var next = new int[size];

    for (int i = 1; i < size; i++)
    {
        var right = i + 1 < size ? a[i + 1] : 0;
        peaks[i] = a[i - 1] < a[i] && a[i] > right;
    }

    next[size - 1] = -1;
    for (int i = size - 2; i >= 0; i--)
    {
        next[i] = peaks[i] ? i : next[i + 1];
    }

    var result = 0;
    for (int i = 1; i * (i - 1) <= size; i++)
    {
        var pos = 0;
        var num = 0;
        while (pos < size && num < i)
        {
            pos = next[pos];
            if (pos == -1)
            {
                break;
            }
            num++;
            pos += i;
        }
        result = Math.Max(result, num);
    }

    return result;
}

defmodule Flags do
  def flags(a) do
    size = length(a)
    a_map = a |> Enum.with_index() |> Map.new(fn {v, i} -> {i, v} end)

    peaks =
      for i <- 1..(size - 1), into: %{} do
        prev = Map.get(a_map, i - 1)
        cur = Map.get(a_map, i)
        nxt = Map.get(a_map, i + 1, 0)
        {i, prev < cur and cur > nxt}
      end

    next_map = build_next(size, peaks)

    search(1, size, next_map, 0)
  end

  defp build_next(size, peaks) do
    Enum.reduce((size - 2)..0//-1, %{size - 1 => -1}, fn i, next_map ->
      value = if Map.get(peaks, i, false), do: i, else: Map.get(next_map, i + 1)
      Map.put(next_map, i, value)
    end)
  end

  defp search(i, size, next_map, result) when i * (i - 1) <= size do
    num = walk(0, i, 0, size, next_map)
    search(i + 1, size, next_map, max(result, num))
  end

  defp search(_i, _size, _next_map, result), do: result

  defp walk(pos, step, num, size, next_map) when pos < size and num < step do
    next_pos = Map.get(next_map, pos)

    if next_pos == -1 do
      num
    else
      walk(next_pos + step, step, num + 1, size, next_map)
    end
  end

  defp walk(_pos, _step, num, _size, _next_map), do: num
end