[Python3] O(N), count by contribution
Whenever sarr[i+1] - sarr[i] > 1, call this a gap.\n\nInstead of asking how many gaps there are in each subarray, let\'s ask for each gap how many subarrays con
Whenever `sarr[i+1] - sarr[i] > 1`, call this a *gap*.\n\nInstead of asking how many gaps there are in each subarray, let\'s ask for each gap how many subarrays contain that gap.\n\nSpecifically, the gap above `A[i]` will exist until we find another `A[i]` or `A[i] + 1`.  Consider subarrays `A[h..j]` for `h <= i <= j` with `h` in `[left[i] + 1, i]` and `j` in `[i, right[i] - 1]` such that they don\'t have these `A[i] + 1`\'s.  There are `(i - left[i]) * (right[i] - i)` such choices of subarray.\n\nActually, we need to check for `A[i]` only on the right to avoid double counting - this would make `i` the location of the rightmost element of `A[i]` in the subarray.\n\nAlso, we subtract `n * (n + 1) // 2` because we\'ve counted each element as having a gap, but actually the maximum element of every subarray doesn\'t have a gap.\n\n# Code\n```\nclass Solution:\n    def sumImbalanceNumbers(self, A: List[int]) -> int:\n        n = len(A)\n\n        left = [-1] * n\n        last = [-1] * (n + 2)\n        for i in range(n):\n            left[i] = last[A[i] + 1]\n            last[A[i]] = i\n\n        right = [n] * n\n        last = [n] * (n + 2)\n        for i in range(n - 1, -1, -1):\n            right[i] = min(last[A[i]], last[A[i] + 1])\n            last[A[i]] = i\n\n        ans = 0\n        for i in range(n):\n            ans += (i - left[i]) * (right[i] - i)\n        return ans - n * (n + 1) // 2\n```
['Python3']