Count The Minimum Once

Given an array of $n$ integers, compute the sum of the minimum of every contiguous subarray. There are $\frac{n(n+1)}{2}$ subarrays and $n$ can be $2 \cdot 10^5$ , so enumerating them is out.

Which reframing is the one that opens the problem?

Binary search on the answer, checking for a candidate total whether it is achievable.

Stop iterating over subarrays and iterate over elements: for each $a_i$ , count how many subarrays have $a_i$ as their minimum, then add $a_i \times \text{count}_i$ . Each count is (distance to the nearest smaller element on the left) times (distance to the nearest smaller element on the right), both computable in one pass with a monotonic stack.

Sort the array ascending, then process elements in order so the current element is always the minimum of what remains.

Keep the subarray loop but maintain a running minimum so each subarray costs $O(1)$ instead of $O(n)$ , which brings the total to $O(n^2)$ .