Compute sum over consecutive-step subarrays

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