A bridge sensor records one temperature reading per hour; the readings are the list temps. Engineers rate every contiguous block of hours temps[i..j] (with i <= j, including single hours) by its stress: the lowest reading in the block multiplied by the highest reading in the block. Return the sum of the stress over all n * (n + 1) / 2 blocks, as an exact integer.
Readings can be negative, so a single block's stress can be negative too.
Examples
Input: temps = [3, 1, 2]
Output: 22
Explanation: [3] 9, [1] 1, [2] 4, [3,1] 3, [1,2] 2, [3,1,2] 3; 9+1+4+3+2+3 = 22.
Input: temps = [-2, 5]
Output: 19
Explanation: 4 + 25 + (-2 * 5) = 19.
Constraints
1 <= len(temps) <= 5 * 10**4-10**9 <= temps[i] <= 10**9- Checking every block one by one takes about a billion steps for the largest inputs and is far too slow.
Goals
- Sum a quantity over all O(n^2) contiguous windows without visiting each window
- Combine windows that cross a split point using monotone prefix minima and maxima
- Keep exact integer arithmetic with negative values and very large totals