救救孩子，挂在 #2 的第 182 个点

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;

int t, n, a[MAXN]; ll m, ans;

int c[MAXN], s[MAXN], top;

int main() {
	for (scanf("%d", &t); t--;) {
		scanf("%d", &n), s[top = 1] = 0, ans = 0;
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]), c[i] = 0;
		a[0] = a[n + 1] = n, n++, scanf("%lld", &m);
		for (int i = 1, x; i <= n; i++) {
			if (a[i] >= a[i - 1]) {
				for (x = a[s[top--]]; top && a[s[top]] <= a[i]; x = a[s[top--]]) c[i - s[top] - 1] += a[s[top]] - x;
				if (top) c[i - s[top] - 1] += a[i] - x;
			}
			s[++top] = i;
		}
		for (int i = n; i; i--) {
			if (!m) break;
			if ((ll)c[i] * i <= m) ans += (ll)c[i] * (i - 1), m -= (ll)c[i] * i;
			else ans += m / i * (i - 1), (m %= i) && (ans += m - 1);
		}
		printf("%lld\n", ans);
	}
}