Sonya - Implementation

function solve(a)
    b[i] = a[i] - i for all i
    cost = 0
    maxHeap = empty

    for i from 1 to n:
        push b[i] to maxHeap
        if maxHeap.top() > b[i]:
            cost += maxHeap.top() - b[i]
            pop from maxHeap
            push b[i] to maxHeap

    return cost

Transform $a$ to $b$ with $b_i = a_i - i$, then process with a heap. The heap tracks slope-change points.

Time: $O(n \log n)$. Space: $O(n)$.