import Data.Array (Array, accumArray, listArray, (!))

numberOfDiscIntersections :: [Int] -> Int
numberOfDiscIntersections a = go 0 0 [0 .. c - 1]
  where
    c   = length a
    arr = listArray (0, c - 1) a :: Array Int Int

    startCounts = accumArray (+) 0 (0, c - 1) [(max 0 (i - arr ! i), 1) | i <- [0 .. c - 1]] :: Array Int Int
    endCounts   = accumArray (+) 0 (0, c - 1) [(min (c - 1) (i + arr ! i), 1) | i <- [0 .. c - 1]] :: Array Int Int

    go _ total [] = total
    go active total (k : ks)
      | total' > 10000000 = -1
      | otherwise          = go active' total' ks
      where
        s       = startCounts ! k
        e       = endCounts ! k
        total'  = total + active * s + (s * (s - 1)) `div` 2
        active' = active + s - e

public class Solution {
    public static int numberOfDiscIntersections(int[] a) {
        int c = a.length;
        long sum = 0;
        long active = 0;
        int[] start = new int[c];
        int[] end = new int[c];

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

            long endKey = (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 (int) sum;
    }
}

(defun number-of-disc-intersections (a)
  (let* ((vec (coerce a 'vector))
         (c (length vec))
         (start (make-array c :initial-element 0))
         (end (make-array c :initial-element 0))
         (sum 0)
         (active 0))
    (loop for k from 0 below c
          for v = (aref vec k)
          do (let ((key1 (if (< k v) 0 (- k v)))
                    (key2 (if (>= (+ k v) c) (1- c) (+ k v))))
               (incf (aref start key1))
               (incf (aref end key2))))
    (loop for k from 0 below c
          do (progn
               (incf sum (+ (* active (aref start k))
                            (/ (* (aref start k) (1- (aref start k))) 2)))
               (incf active (- (aref start k) (aref end k)))
               (when (> sum 10000000)
                 (return-from number-of-disc-intersections -1))))
    sum))

function numberOfDiscIntersections(array $a): int
{
    $sum   = $active = 0;
    $c     = count($a);
    $start = $end = array_fill(0, $c, 0);

    foreach ($a as $k => $v) {
        $key = $k < $v ? 0 : $k - $v;
        $start[$key]++;

        $key = $k + $v >= $c ? $c - 1 : $k + $v;
        $end[$key]++;
    }

    foreach ($a as $k => $v) {
        $sum    += $active * $start[$k] + ($start[$k] * ($start[$k] - 1)) / 2;
        $active += $start[$k] - $end[$k];
        if ($sum > 10000000) {
            return -1;
        }
    }

    return $sum;
}

def number_of_disc_intersections(a: list[int]) -> int:
    c = len(a)
    start = [0] * c
    end = [0] * c

    for k, v in enumerate(a):
        key = 0 if k < v else k - v
        start[key] += 1

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

    total = 0
    active = 0
    for k in range(c):
        total += active * start[k] + (start[k] * (start[k] - 1)) // 2
        active += start[k] - end[k]
        if total > 10000000:
            return -1

    return total

fn number_of_disc_intersections(a: &[i64]) -> i64 {
    let c = a.len();
    let mut start = vec![0i64; c];
    let mut end = vec![0i64; c];

    for (k, &v) in a.iter().enumerate() {
        let k = k as i64;
        let key = if k < v { 0 } else { (k - v) as usize };
        start[key] += 1;

        let key = if k + v >= c as i64 { c - 1 } else { (k + v) as usize };
        end[key] += 1;
    }

    let mut sum = 0i64;
    let mut active = 0i64;
    for k in 0..c {
        sum += active * start[k] + (start[k] * (start[k] - 1)) / 2;
        active += start[k] - end[k];
        if sum > 10_000_000 {
            return -1;
        }
    }

    sum
}

function numberOfDiscIntersections(a: number[]): number {
  let sum = 0;
  let active = 0;
  const c = a.length;
  const start: number[] = new Array(c).fill(0);
  const end: number[] = new Array(c).fill(0);

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

    const endKey = k + v >= c ? c - 1 : k + v;
    end[endKey]++;
  }

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

  return sum;
}

odd_occurrences_in_array() {
    local -n _a="$1"
    local -A _count
    local _v
    for _v in "${_a[@]}"; do
        if [[ -z "${_count[$_v]:-}" ]]; then
            _count[$_v]=1
        else
            unset '_count[$_v]'
        fi
    done
    for _v in "${!_count[@]}"; do
        echo "$_v"
        return
    done
}

#include <optional>
#include <unordered_map>
#include <vector>

std::optional<int> oddOccurrencesInArray(const std::vector<int>& a)
{
    std::unordered_map<int, int> count;
    std::vector<int> order; // preserves first-seen order, like PHP's insertion-ordered array

    for (int value : a) {
        auto it = count.find(value);
        if (it == count.end()) {
            count[value] = 1;
            order.push_back(value);
        } else {
            count.erase(it);
        }
    }

    for (int v : order) {
        if (count.find(v) != count.end()) {
            return v;
        }
    }

    return std::nullopt;
}

static int? OddOccurrencesInArray(int[] a)
{
    var count = new Dictionary<int, int>();

    foreach (var value in a)
    {
        if (!count.ContainsKey(value))
        {
            count[value] = 1;
        }
        else
        {
            count.Remove(value);
        }
    }

    return count.Count > 0 ? count.Keys.First() : (int?)null;
}