Picture lines in a plane. The lower envelope zigzags through them. You maintain this envelope in a deque. As you process states left-to-right:
Query: Your pointer slides right. Pop lines from the front that are no longer optimal.
Insert: Add the new line at the back. Pop any lines it dominates. Think of it as a sliding window on the envelope. The window only moves forward. That's why it's .