defmodule Peaks do
  def peaks(a) when length(a) <= 2, do: 0

  def peaks(a) do
    n = length(a)
    a_map = a |> Enum.with_index() |> Map.new(fn {v, i} -> {i, v} end)

    {sum, dist, last_peak} = scan_peaks(a_map, n)
    total_peaks = Map.get(sum, n - 2, 0)
    sum = Map.put(sum, n - 1, total_peaks)

    if total_peaks == 0 do
      0
    else
      dist = max(dist, n - last_peak)

      case find_divisor(div(dist, 2) + 1, dist, n, sum) do
        {:ok, groups} -> groups
        :none -> div(n, find_valid_divisor(dist, n))
      end
    end
  end

  defp scan_peaks(a_map, n) do
    Enum.reduce(1..(n - 2), {%{0 => 0}, 0, -1}, fn i, {sum, dist, last} ->
      prev_sum = Map.get(sum, i - 1)

      is_peak =
        Map.get(a_map, i) > Map.get(a_map, i - 1) and
          Map.get(a_map, i) > Map.get(a_map, i + 1)

      if is_peak do
        {Map.put(sum, i, prev_sum + 1), max(dist, i - last), i}
      else
        {Map.put(sum, i, prev_sum), dist, last}
      end
    end)
  end

  defp find_divisor(i, dist, _n, _sum) when i >= dist, do: :none

  defp find_divisor(i, dist, n, sum) do
    if rem(n, i) == 0 do
      case walk_groups(i, i, n, sum, 0) do
        {:ok, last_j} when last_j > n -> {:ok, div(n, i)}
        _ -> find_divisor(i + 1, dist, n, sum)
      end
    else
      find_divisor(i + 1, dist, n, sum)
    end
  end

  defp walk_groups(j, _step, n, _sum, _last) when j > n, do: {:ok, j}

  defp walk_groups(j, step, n, sum, last) do
    current = Map.get(sum, j - 1)

    if current <= last do
      {:ok, j}
    else
      walk_groups(j + step, step, n, sum, current)
    end
  end

  defp find_valid_divisor(last, n) when rem(n, last) == 0, do: last
  defp find_valid_divisor(last, n), do: find_valid_divisor(last + 1, n)
end