In case anyone wants to submit their solution, the problem is here. (with n <= 3e5)

Here is a rough outline for how you can find the answer for all subsegments which cover index $$$m = (l + r)/2$$$ for fixed subsegment $$$[l, r]$$$ in your recursion:

1. Build suffix min/max array for $$$[l, m]$$$ and prefix min/max for $$$[m, r]$$$. Also build suffix sum array of suffix maximums of $$$[l, m]$$$ and analogous prefix array for $$$[m, r]$$$.
2. First, we find the sum for segments for which minimum lies in left half. Iterate over suffix $$$s$$$ of left half. Let suffix minimum of $$$s$$$ be $$$x$$$. Now, you can only include prefixes from right half which have minimum $$$\geq x$$$ (there will exist some $$$j$$$ such that all prefixes with length $$$\leq j$$$ in right half will have minimum $$$\geq x$$$, find this by binary search). There will also exist some $$$k \leq j$$$ such that the prefix maximum of all prefixes in right half with length $$$\leq k$$$ will be smaller than the suffix maximum of $$$s$$$ (find this with binary search too). Now simply add the contribution of this suffix (using the arrays you built).
3. Process the case when minimum lies in right half symmetrically (note that you need to carefully handle the case where minimum from both halves is equal).