function nesting(string $s): int
{
    if (empty($s)) {
        return 1;
    }
    $stack = [];
    foreach (str_split($s) as $v) {
        if ($v === ')') {
            if (empty($stack) || array_pop($stack) !== '(') {
                return 0;
            }
        } elseif ( ! empty($v)) {
            $stack[] = $v;
        }
    }

    return empty($stack) ? 1 : 0;
}

def nesting(s: str) -> int:
    if not s:
        return 1

    stack: list[str] = []
    for ch in s:
        if ch == ")":
            if not stack or stack.pop() != "(":
                return 0
        elif ch:
            stack.append(ch)

    return 1 if not stack else 0

fn nesting(s: &str) -> i64 {
    if s.is_empty() {
        return 1;
    }

    let mut stack = Vec::new();
    for c in s.chars() {
        if c == ')' {
            if stack.pop() != Some('(') {
                return 0;
            }
        } else {
            stack.push(c);
        }
    }

    if stack.is_empty() { 1 } else { 0 }
}

function nesting(s: string): number {
  if (s === "") {
    return 1;
  }

  const stack: string[] = [];
  for (const v of s) {
    if (v === ")") {
      if (stack.length === 0 || stack.pop() !== "(") {
        return 0;
      }
    } else if (v) {
      stack.push(v);
    }
  }

  return stack.length === 0 ? 1 : 0;
}

number_of_disc_intersections() {
    local -n _a="$1"
    local _c=${#_a[@]}
    local -a _start _end
    local _k
    for ((_k = 0; _k < _c; _k++)); do _start[_k]=0; _end[_k]=0; done
    for _k in "${!_a[@]}"; do
        local _v=${_a[$_k]}
        local _key
        if (( _k < _v )); then _key=0; else _key=$(( _k - _v )); fi
        (( _start[_key]++ ))
        if (( _k + _v >= _c )); then _key=$(( _c - 1 )); else _key=$(( _k + _v )); fi
        (( _end[_key]++ ))
    done
    local _sum=0 _active=0
    for ((_k = 0; _k < _c; _k++)); do
        _sum=$(( _sum + _active * _start[_k] + (_start[_k] * (_start[_k] - 1)) / 2 ))
        _active=$(( _active + _start[_k] - _end[_k] ))
        if (( _sum > 10000000 )); then
            echo -1
            return
        fi
    done
    echo "$_sum"
}

#include <vector>

long long numberOfDiscIntersections(const std::vector<int>& a)
{
    long long sum = 0;
    long long active = 0;
    int c = static_cast<int>(a.size());
    std::vector<int> start(c, 0);
    std::vector<int> end(c, 0);

    for (int k = 0; k < c; ++k) {
        long long v = a[k];

        long long key = (k < v) ? 0 : k - v;
        ++start[static_cast<int>(key)];

        long long key2 = (static_cast<long long>(k) + v >= c) ? c - 1 : k + v;
        ++end[static_cast<int>(key2)];
    }

    for (int k = 0; k < c; ++k) {
        sum += active * start[k] + (static_cast<long long>(start[k]) * (start[k] - 1)) / 2;
        active += start[k] - end[k];
        if (sum > 10000000) {
            return -1;
        }
    }

    return sum;
}

static long NumberOfDiscIntersections(int[] a)
{
    long sum = 0;
    long active = 0;
    var c = a.Length;
    var start = new int[c];
    var end = new int[c];

    for (int k = 0; k < c; k++)
    {
        var v = a[k];
        var startKey = k < v ? 0 : k - v;
        start[startKey]++;

        var endKey = (long)k + v >= c ? c - 1 : k + v;
        end[(int)endKey]++;
    }

    for (int k = 0; k < c; k++)
    {
        sum += active * start[k] + (long)start[k] * (start[k] - 1) / 2;
        active += start[k] - end[k];
        if (sum > 10000000)
        {
            return -1;
        }
    }

    return sum;
}

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

-module(number_of_disc_intersections).
-export([number_of_disc_intersections/1]).

number_of_disc_intersections(A) ->
    C = length(A),
    Indexed = lists:zip(lists:seq(0, C - 1), A),
    {Start, End} = lists:foldl(fun({K, V}, {S, E}) ->
        KeyS = case K < V of true -> 0; false -> K - V end,
        KeyE = case K + V >= C of true -> C - 1; false -> K + V end,
        {array:set(KeyS, array:get(KeyS, S) + 1, S),
         array:set(KeyE, array:get(KeyE, E) + 1, E)}
    end, {array:new(C, {default, 0}), array:new(C, {default, 0})}, Indexed),
    compute_sum(0, 0, 0, C, Start, End).

compute_sum(K, _Active, Sum, C, _Start, _End) when K >= C ->
    Sum;
compute_sum(K, Active, Sum, C, Start, End) ->
    StartK = array:get(K, Start),
    EndK = array:get(K, End),
    Sum1 = Sum + Active * StartK + (StartK * (StartK - 1)) div 2,
    case Sum1 > 10000000 of
        true -> -1;
        false -> compute_sum(K + 1, Active + StartK - EndK, Sum1, C, Start, End)
    end.

func numberOfDiscIntersections(a []int) int {
	c := len(a)
	start := make([]int, c)
	end := make([]int, c)

	for k, v := range a {
		key := k - v
		if k < v {
			key = 0
		}
		start[key]++

		key = k + v
		if k+v >= c {
			key = c - 1
		}
		end[key]++
	}

	sum, active := 0, 0
	for k := range a {
		sum += active*start[k] + (start[k]*(start[k]-1))/2
		active += start[k] - end[k]
		if sum > 10000000 {
			return -1
		}
	}

	return sum
}