What if values come in arbitrary order? The front-popping trick fails because you might need a "popped" line later. Two solutions:
Binary search: Keep all lines on the envelope. For query , binary search for the segment containing . per query.
Li Chao tree: A segment tree where each node stores a line. Insert and query both take . The deque still works for insertions (if slopes are sorted). Only queries change.