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