【题意】
给你一个长度为$n$的全为0的序列$a_i$，每次可以选择一个$k$，使得前$k$个或者后$k$个$a_i$加上1，操作代价为$k$，现在让你用最小的代价使得$a_i>=b_i$

【思路】
想了一个上午，主要是突破口不好找，找到突破口以后很快就能出来。

要考虑若干个前缀和若干个后缀能够形成的序列形态。

比如固定有$x$个前缀和$y$个后缀，那么这个序列从左往右就是从$x$开始可以有$x$次减少1，和$y$次增加1。

然后发现只要减少1是需要固定的（也就是固定$x$），增加1完全可以看情况来决定。

现在考虑固定$x$然后求贡献，我们先假设从x开始只能增加，不能减少，那么最好的方法肯定就是从左往右遇到比自己更高的就增加到这个高度（初始高度为$x$）。

然后就要找$x$个位置减少，使得减少的总量最多，很明显对于不同的$x$这些可以减少的位置都是固定的，因此可以先处理出来然后再枚举$x$来求。

【代码】

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e6 + 10, inf = 1e9 + 10;int n, a[N];
pair<int, int> b[N]; int cnt;
int tp, sta[N];
int zuo[N], you[N];void solve() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}a[0] = a[n + 1] = inf;sta[tp = 0] = 0;for (int i = 1; i <= n; i++) {while (tp && a[sta[tp]] < a[i]) tp--;zuo[i] = sta[tp];sta[++tp] = i;}sta[tp = 0] = n + 1;for (int i = n; i >= 1; i--) {while (tp && a[sta[tp]] <= a[i]) tp--;you[i] = sta[tp];sta[++tp] = i;}cnt = 0;for (int i = 1; i <= n; i++) {if (!zuo[i] || a[zuo[i]] == a[i]) continue;int up = min(a[zuo[i]], a[you[i]]);b[++cnt] = {you[i] - zuo[i] - 1, up - a[i]};}sort(b + 1, b + cnt + 1);// cout << cnt << endl;// for (int i = 1; i <= cnt; i++) {//     cout << b[i].first << " " << b[i].second << endl;// }sta[tp = 1] = 1;for (int i = 2; i <= n + 1; i++) {if (a[i] > a[sta[tp]]) {sta[++tp] = i;}}ll ans = 0;for (int i = 1; i < tp; i++) {ans += 1ll * (sta[i + 1] - sta[i]) * a[sta[i]];}a[sta[0] = 0] = 0;for (int i = 1; i < tp; i++) {int temp = a[sta[i]] - a[sta[i - 1]];int d = sta[i] - 1;while (cnt && temp && b[cnt].first > d) {int t = min(b[cnt].second, temp);ans -= 1ll * t * (b[cnt].first - d);b[cnt].second -= t; if (!b[cnt].second) cnt--;temp -= t;}}cout << ans << endl;
}int main() {// freopen("in.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);int T; cin >> T;while (T--) {solve();}
}