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