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).