Sum of Every Range — Solution & Editorial

Back to the Problem

Sum-of-ranges = (sum of all subarray maxima) − (sum of all subarray minima); each is a contribution count via monotonic stacks.

Complexity: O(N)

Watch out: The total reaches ~10⁹·N² ≈ 10¹⁹ — beyond signed 64-bit; use unsigned/128-bit (Python is safe).