CHT Query - Walkthrough

Deque has lines with intersections at $x = 3, 7, 12$. Query for $x = 10$. Binary search: $10 > 3$, $10 > 7$, $10 < 12$. The optimal line is between intersections 7 and 12.

With sorted queries: if last query was $x = 8$, pointer was at line after intersection 7. For $x = 10$, pointer stays (still before intersection 12). Amortized $O(1)$ per query: pointer only moves right. Total movement across all queries is $O(n)$.