Compute sum over consecutive-step subarrays
Company: Google
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array `a` of length `n`, call a subarray `a[l..r]` **good** if either:
- it is strictly increasing by 1 at every step: `a[i+1] - a[i] = 1` for all `i in [l, r-1]`, **or**
- it is strictly decreasing by 1 at every step: `a[i+1] - a[i] = -1` for all `i in [l, r-1]`.
(All length-1 subarrays are good.)
Define the value of a subarray as the **sum of its elements**. Return the **sum of values of all good subarrays**.
### Requirements
- Time complexity: **O(n)**
- Use 64-bit integer arithmetic for the result.
### Example
Input: `a = [3, 5, 6, 7, 6]`
Good subarrays are:
- `[3]`, `[5]`, `[6]`, `[7]`, `[6]`
- `[5, 6]`, `[6, 7]`, `[5, 6, 7]`, `[7, 6]`
Output: `82`
### Constraints (you may assume)
- `1 <= n <= 2 * 10^5`
- `|a[i]| <= 10^9`
Quick Answer: This question evaluates proficiency in array processing, detection of consecutive-step arithmetic sequences, and accumulation of subarray sums with attention to large-integer (64-bit) arithmetic.