Process elements left-to-right. For each , push it to the heap. If , the array isn't non-decreasing yet.
Pop the largest value, pay the cost to reduce it to , then push again. Why twice? The first push represents itself. The second accounts for the slope change from merging the popped value. Each element is pushed once initially. Extra pushes balance slope changes. Total operations: .