Assume . As increases, the optimal line can only move right on the envelope (or stay the same). Why? Lines are sorted by slope on the envelope. A line with smaller slope beats others for small . As grows, lines with larger slopes take over.
Once a line stops being optimal, it never comes back. This monotonicity means you never revisit old lines. A simple pointer suffices. Even simpler: use a deque.