defmodule NumberOfDiscIntersections do
  def number_of_disc_intersections(a) do
    c = length(a)

    {starts, ends} =
      a
      |> Enum.with_index()
      |> Enum.reduce({%{}, %{}}, fn {v, k}, {starts, ends} ->
        start_key = max(0, k - v)
        end_key = min(c - 1, k + v)

        {Map.update(starts, start_key, 1, &(&1 + 1)), Map.update(ends, end_key, 1, &(&1 + 1))}
      end)

    0..(c - 1)
    |> Enum.reduce_while({0, 0}, fn k, {sum, active} ->
      s = Map.get(starts, k, 0)
      e = Map.get(ends, k, 0)
      sum = sum + active * s + div(s * (s - 1), 2)

      if sum > 10_000_000 do
        {:halt, {:found, -1}}
      else
        {:cont, {sum, active + s - e}}
      end
    end)
    |> case do
      {:found, -1} -> -1
      {sum, _active} -> sum
    end
  end
end