Sonya - Transform Trick

Strictly increasing means $a_1 < a_2 < \ldots < a_n$. This is hard to work with. Transform it: let $b_i = a_i - i$. Now you want $b$ to be non-decreasing instead.

Why? If $b_1 \leq b_2 \leq \ldots \leq b_n$, then $a_1 < a_2 < \ldots < a_n$ automatically. The cost stays the same: changing $a_i$ to $x$ is the same as changing $b_i$ to $x - i$. This transform converts strict inequality to non-strict. Now you can use the classic non-decreasing array technique with heaps.