Why O(n) Total

Each line is added exactly once and removed at most once. That's $O(n)$ add operations, $O(n)$ remove operations. Adding: You might pop multiple lines when adding one, but total pops across all adds is bounded by total lines ever added. That's $O(n)$. Querying: Same logic.

Each front-pop happens at most once per line. Total query overhead: $O(n)$. Combined: $O(n)$ time for $n$ states. Your $O(n^2)$ DP becomes $O(n)$ because we do $O(n)$ work total, not $O(n)$ work per state. That's the power of CHT.