关键观察

修改最多 K 个位置，等价于保留至少 n-K 个位置不变，并把被修改的位置随意设置，使整个序列满足相邻差不超过 x。 选择一组下标递增的保留位置 $i_1<i_2<\cdots<i_m$；且这些位置的原高度都保留，那么想让中间被修改的位置“补”出来使整段满足条件，必要且充分的是：对所有 p<q，有

这条条件保证了可以用步长不超过 x 的“线性插值”把中间位置填上。 于是，固定某个 x，问题化为：求一个最长的下标序列，使得任意两点满足上式；记其长度为 L(x)。最少修改数就是 n-L(x)，可行性的判定为

题目内容

小红正在玩一个游戏：这个游戏他需要从左往右依次经过 $n$ 座山，其中第 $i$ 座山的高度为 $h_i$ 。在游戏开始之前，他需要装备耐久足够高的登山鞋才行。

假设小红装备的登山鞋的耐久度为 $x$ ，那么如果存在一个 $i(1≤i<n),|h_{i+1}-h_i|>x$ ，那么小红就无法攀爬下一座山。也就是说，任意相邻的两座山的高度之差不能超过 $x$ 。

游戏正式开始之前，他利用前面关卡获得经验值来购买了 $k$ 次操作，其中每一次操作都可以修改任意一座山的高度，并且可以将其修改为任意非负整数高度。他想知道：自己能够装备的登山鞋的耐久度最低可以是多少?