When Queries Are Sorted

Assume $x_1 \leq x_2 \leq \ldots \leq x_n$. As $x$ increases, the optimal line can only move right on the envelope (or stay the same). Why? Lines are sorted by slope on the envelope. A line with smaller slope beats others for small $x$. As $x$ grows, lines with larger slopes take over.

Once a line stops being optimal, it never comes back. This monotonicity means you never revisit old lines. A simple pointer suffices. Even simpler: use a deque.