You maintain two heaps: max-heap for left slopes, min-heap for right slopes. The max-heap top gives the rightmost point with negative slope. The min-heap top gives the leftmost point with positive slope.
When you add , push into both heaps. Then balance: if max-heap.top() > min-heap.top(), you've created an invalid setup. Pop from both until ordered correctly. This keeps the function convex and lets you query the minimum location. The heaps store all slope-change points without computing function values.