People stand in a single file facing a stage; heights[0] is closest to the stage. Whenever
a person at position i is strictly taller than a person at a later position j
(i < j), that pair costs heights[i] - heights[j] centimetres of blocked view.
Return the total over all such pairs. Pairs of equal height cost nothing.
Examples
Input: heights = [5, 3, 4]
Output: 3
Explanation: (5, 3) costs 2 and (5, 4) costs 1. The 3 in front of the 4 costs nothing.
Input: heights = [2, 2, 1]
Output: 2
Constraints
0 <= len(heights) <= 4 * 10**41 <= heights[i] <= 10**9- Target complexity: O(n log n). Visiting every pair is too slow for the largest inputs.
Goals
- Add up the size of every out-of-order pair, not just count the pairs
- Carry a running sum through the merge step
- Make sure equal heights contribute nothing