Sonya - Walkthrough

Make array non-decreasing with minimum cost (sum of changes). Transform: $b_i = a_i - i$. Now make $b$ non-decreasing but with the same values allowed. $dp[i][x]$ = min cost for first $i$ elements, last value is $x$.

Transition: $dp[i][x] = \min_{y \leq x}(dp[i-1][y]) + |x - b_i|$. The $\min_{y \leq x}$ is a prefix min. The $|x - b_i|$ adds a V-shape centered at $b_i$. Heap operations: prefix $min = remove$ all right breakpoints beyond the min point. Add $V = add$ $b_i$ to both heaps, balance.