When Queries Aren't Sorted

What if $x_i$ values come in arbitrary order? The front-popping trick fails because you might need a "popped" line later. Two solutions:

$1.$ Binary search: Keep all lines on the envelope. For query $x$, binary search for the segment containing $x$. $O(\log n)$ per query.

$2.$ Li Chao tree: A segment tree where each node stores a line. Insert and query both take $O(\log n)$. The deque still works for insertions (if slopes are sorted). Only queries change.