Sonya - Heap Operations

Process elements left-to-right. For each $b_i$, push it to the heap. If $b_i < \text{heap.top()}$, the array isn't non-decreasing yet.

Pop the largest value, pay the cost to reduce it to $b_i$, then push $b_i$ again. Why twice? The first push represents $b_i$ 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(n \log n)$.