Querying the Minimum

To query at $x_i$:

$1.$ While the deque has $\geq 2$ lines, check if the second line is better than the first at $x_i$.

$2.$ If $L_2(x_i) < L_1(x_i)$, pop the front. The first line will never be optimal again because queries are increasing.

$3.$ Repeat until the front is optimal.

$4.$ Return $L_1(x_i)$. Because queries are sorted, once you pop a line, you never need it again. Each line leaves the deque at most once.