Process elements left-to-right. For each , push it to the max-heap. If , the array violates non-decreasing.
Pop the largest previous value, pay the cost , then push 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 without computing all values.