首先 \(a_i\gets a_i-i\)，预先考虑严格递增的限制，接下来只需要不降即可。
考虑在一个不降的序列后面加入一个数 \(x\)，如果之前的最大值 \(y>x\)，那么需要确定一个基准数 \(k\)，花费 \(y-x\) 的代价使得 \(x,y\gets k\)。
贪心地考虑，为了花费尽可能小的代价使得最终序列不降，\(k\) 选取得越小越好，不过这取决于以下两点：
- \(k<x\) 的情况可以后续处理，所以 \(x\leq k\leq y\)。
- 当 \(y\) 前面的最大值 \(z\) 满足 \(z>k\) 时，这样修改并不能保证序列不降。
不过 \(k\leq z\) 是可以确定的，这样就使得全局最大值从 \(y\) 变成了 \(z\)。
考虑反悔。一直做，当前面的 \(z\) 全部被降到更低后，别忘了当前这组可变化的范围仍是 \([x,y]\)。相当于可以在无代价的情况下将 \(y\) 和 \(x\) 变成比 \(z\) 更小的数。
显然，在这个过程中我们并没有用到关于 \(x\) 和 \(y\) 的任何信息直到全局最大值小于等于 \(x\)。
那么我们在处理的时候直接将 \(y\) 改成 \(x\) 就能保证最优。