854. The Total Spread Over Every Stretch

The SPREAD of a contiguous stretch is its largest value minus its smallest value. Read n values and print the sum of the spreads of all n(n+1)/2 stretches. A single element has spread 0.

1 2 3 -> 4 4 -2 -3 4 1 -> 59 2 2 2 2 -> 0

For 1 2 3 the stretches of length 1 contribute 0, the two of length 2 contribute 1 each, and the whole row contributes 2, giving 4.

## Splitting one hard sum into two easy ones

The spread is a difference, and summation distributes over a difference:

sum of spreads = ( sum over stretches of the maximum ) - ( sum over stretches of the minimum )

Each half is a contribution problem of exactly the kind in problem 853. Running that machinery twice, once with the comparisons pointing one way and once the other, solves the whole thing.

That split is the entire idea. Trying to attack max - min directly, as a single quantity, leads nowhere useful, because the position of the maximum and the position of the minimum move independently.

## The four boundaries

For the minimum half, credit each stretch to the EARLIEST position holding its minimum:

countMin[i] = (i - prevSmallerOrEqual(i)) * (nextStrictlySmaller(i) - i)

For the maximum half, credit it to the earliest position holding its maximum:

countMax[i] = (i - prevGreaterOrEqual(i)) * (nextStrictlyGreater(i) - i)

so four stack passes in total: two increasing stacks for the minima and two DECREASING stacks for the maxima. Reusing the same helper with the comparison passed in is the tidy way to write it, and it makes the symmetry obvious.

## The check that catches a mismatched tie rule

Each set of counts must sum to n(n+1)/2 independently. If the two halves use tie rules that do not match, both sums can still look plausible while the difference is wrong, and the failure only shows on inputs with repeated values. The row 2 2 2 2 must answer 0, and it answers 0 only when the two halves credit the same stretch to the same position.

## Negatives and size

Values may be negative, so nothing here may assume a zero baseline. The minima half can be negative on its own; only the difference is guaranteed non-negative.

With n = 100000 and values up to 10^4 in absolute size, the total reaches roughly 10^14. That fits in a signed 64-bit integer but not in 32 bits, and there is no remainder to hide behind here, so the type has to be right.

## Related problems

Problem 853 is the minima half on its own with a modulus. Problem 847 prints the counts rather than using them.

## Cost

Time O(n), four stack passes. Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `-10^4 ≤ a[i] ≤ 10^4` - the answer can reach `10^14`, so it needs 64 bits