dp[i] as a function of v (the value of ai) is convex and piecewise linear. Initially, dp[0](v)=∣v−a0∣, a V-shape centered at a0.
Adding ∣v−ai∣ keeps convexity. The constraint "v≥previous value" truncates the function on the left, preserving only the non-decreasing part. The minimum of dp[i] is at the largest breakpoint less than or equal to the current choice. A max-heap tracks these breakpoints.