我们发现这种最大值最小化的题目最适合 二分 了。

首先，我们二分这个 $z$ 的值，然后再去想想二分答案的 check 怎么写。

转化一下条件：

$$|x_i - x_{i+1}| \le z \implies -z \le x_i - x_{i+1} \le z$$

由于我们只能把数变小，所以就变成：

• 从左往右看：即 $x_i \le x_{i-1} + z$。
• 从右往左看：即 $x_i \le x_{i+1} + z$。

把两边的限制取交集 $h[i] = \min(l[i], r[i])$，我们就得到了在当前 $z$ 的限制下，整个序列能保持的最高高度。

然后我们研究该怎么使得其中一个高度为 0。

我们直接枚举验证。

如果把 $h[k]$ 强行变到 0，由于高差不能超过 $z$，它的邻居们就会受到连锁反应：

• $h[i] > |k - i| \times z$ 的时候要减

利用单调性，随着 $k$ 的右移，受影响的左边界 $L$ 和右边界 $R$ 也是单调右移的。因此我们可以使用双指针（滑动窗口）在 $\mathcal{O}(n)$ 的时间内求出所有 $k$ 对应的边界：

• 左边界 $L$：满足 $h[L] > (k - L) \times z$ 的最小 $L$。
• 右边界 $R$：满足 $h[R] > (R - k) \times z$ 的最大 $R$。

确定边界后，由于塌陷后的地形是一个标准的等差数列，我们可以利用前缀和 $s[i]$ 在 $\mathcal{O}(1)$ 的时间内算出该区间的额外代价。

Code :

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int n, a[N], l[N], r[N], h[N], cl[N], cr[N];
ll m, s[N];
int check(int x){
	l[1] = a[1];
	for(int i = 2; i <= n; i++) l[i] = min(a[i], l[i - 1] + x);
	r[n] = a[n];
	for(int i = n - 1; i ; i--) r[i] = min(a[i], r[i + 1] + x);
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		h[i] = min(l[i], r[i]);
		ans += 1ll * (a[i] - h[i]);
		s[i] = s[i - 1] + h[i];
	}
	if(ans > m) return -1;
	int L = 1;
	for(int k = 1; k <= n; k++) {
		while(L < k && h[L] <= (k - L) * x) L++;
		cl[k] = L;
	}
	int R = n;
	for(int k = n; k >= 1; k--) {
		while(R > k && h[R] <= (R - k) * x) R--;
		cr[k] = R;
	}
	for(int k = 1; k <= n; k++) {
		if(h[k] == 0){
			if(ans <= m) return k;
			continue;
		}
		ll res = 0;
		if(cl[k] < k){
			ll cnt = k - cl[k];
			res += (s[k] - s[cl[k] - 1]) - 1ll * x * (cnt + 1) * cnt / 2;
		} else {
			res += h[k];
		}
		if(cr[k] > k){
			ll cnt = cr[k] - k;
			res += (s[cr[k]] - s[k]) - 1ll * x * (cnt + 1) * cnt / 2;
		}
		if(res + ans <= m) return k;
	}
	return -1;
}
int main(){
	scanf("%d %lld", &n, &m);
	int mx = 0;
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]), mx = max(mx, a[i]);
	ll l = 0, r = mx, ans = mx, P = 1;
	while(l <= r) {
		int mid = l + r >> 1;
		int p = check(mid);
		if(p != -1) r = mid - 1, ans = mid, P=p;
		else l = mid + 1;
	}
	printf("%lld %lld\n", P, ans);
	return 0;
}