CSES - Heap Mechanics

Process elements left-to-right. For each $a_i$, push it to the max-heap. If $a_i < \text{heap.top()}$, the array violates non-decreasing.

Pop the largest previous value, pay the cost $\text{heap.top()} - a_i$, then push $a_i$ again. The double-push maintains the correct number of slope-change points. Why does this work? The heap represents the piecewise linear function. Popping and pushing adjust the slope at $a_i$ without computing all values.