此题有nlogn的贪心解法，但理解起来比较有难度。我们通过例子来解释。我们先考虑如何实现一个非递减序列。
假设数组前三个元素已经是2,6,8，那么我们必须不需要任何操作。
如果第四个元素是5，那么我们要让最后两个元素“非递减”，无论如何至少要消耗三次操作。比如将第四个元素升为8。此外还有其他的操作，比如将最后两个元素都变成6，将最后两个元素都变成7，等等。这些操作的代价都相同，即都是3. 在这里，为了在后续更容易地构造“非递减”序列，我们这就保守地将第三和第四个元素都变成5（同样花费3个代价）。此时我们将序列写作
idx 1, 2, (3, 4)
val 2, 6, 5
注意，这里我们将第三个元素和第四个元素“捆绑”在一起，让它们今后“共进退”，也就是永远取相同的值，这样能够让后面的元素更容易地“递增”地接上去。
此时会说，这样的序列并不是“非递减”的呀。没关系，之前我们分析过(3,4)这两个元素，我们可以让它们都是5，也可以让它们都是6，也可以让它们都是7或者8，这些方案都不改变之前付出的代价3，我们称之为“弹性范围”. 我们现在只是标注了弹性范围的下限，而它们其实可以在不增加消耗地前提下，匹配它们前面的任意元素的值，比如说6，就可以与第二个元素相接了成为“非递增”了. 事实上，无论如何，(3,4)这两个元素一定可以“无代价”地与之前的元素成功相接：这是因为(3,4)两个元素弹性变化范围的上限是8，而8是之前序列里的最大元素，6只不过是次大元素，所以定会在(3,4)两个元素的弹性变化范围内。
我们继续这个例子，假如第五个元素是4。此时数组里的最大元素是第二个的6，所以我们必然想把4提升到6，或者把6降到4. 所以我们至少需要2个代价。换而言之，我们用2个代价，可以将(2,5)这两个元素在4,5,6之间弹性变化。我们记做
idx 1, (3, 4), (2, 5)
val 2, 5, 4
同样，我们虽然标记了4，但是因为(2,5)这两个元素的弹性范围是4~6，它必然可以在需要的时候与之前的(3,4)匹配（因为5是之前的次大值，小于6）。所以至此，我们用了3+2=5个必须付出的代价，但理论上可以保证前5个元素一定可以调整为“非递减”序列。
这里再说明一下，为什么我们总标记弹性区间的下限呢？当然是为了贪心地好让后面的元素以更小的代价接上来呀。
以后再遇到新的数字，步骤就与之前完全一致了。如果新元素比val数组里的所有元素都大，那么索性无代价地加入（反正以后还有机会削减）。如果新元素比val数组里的最大值小，那么我们就特意将最大值的元素与新元素“捆绑”处理（约定相同的值），并可以得到一个弹性区间（弹性区间内的代价不变）。区间的下限就是新元素的值，上限就是刚才的最大值。注意我们将捆绑后的元素放入val数组里的时候，只标记下限。此时我们一定有结论：最新捆绑的元素一定可以变换到某个数值，能与之前的元素拼接成“非递减”序列。
将以上的思路整理一下，程序只需要一个优先队列即可实现。