Process elements left-to-right. For each bi, push it to the heap. If bi<heap.top(), the array isn't non-decreasing yet.
Pop the largest value, pay the cost to reduce it to bi, then push bi again. Why twice? The first push represents bi 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: O(nlogn).