30分求调

#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int N = 1e6 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL n, a[N];
LL lmx[N], rmx[N], dep[N];

int main()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	
	int _;
	cin >> _;
	while (_--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		
		lmx[1] = a[1];
		for (int i = 2; i <= n; i++) {
			lmx[i] = max(lmx[i - 1], a[i]);
		}
		rmx[n] = a[n];
		for (int i = n - 1; i > 0; i--) {
			rmx[i] = max(rmx[i + 1], a[i]);
		}
		LL sum = 0;
		for (int i = 1; i <= n; i++) {
			dep[i] = min(lmx[i], rmx[i]) - a[i];	//cout<<dep[i]<<' ';
			sum += dep[i];
		}
		
		LL ans = INF;
		// 把i改成很大的数
		for (int i = 1; i <= n; i++) {
			ans = min(ans, sum - dep[i]);
		}
		// 如果a[i] == lmx[i]，把i改成lmx[i - 1]
		LL drop = 0, gap = 0;	// 当前漏走多少水，要漏水至少要有多高
		for (int i = 1; i <= n; i++) {
			if (a[i] == lmx[i]) {	// 作为开始漏水的起点
				ans = min(ans, sum - drop);
				drop = 0;
				gap = lmx[i - 1];
//				gap = i == 1 ? a[2] : lmx[i - 1];
			} else {
				if (gap < a[i]) {
					gap = a[i];
				}
				drop += a[i] + dep[i] - gap;
			}
		}
		drop = 0, gap = 0;
		for (int i = n; i > 0; i--) {
			if (a[i] == rmx[i]) {
				ans = min(ans, sum - drop);
				drop = 0;
				gap = rmx[i + 1];
//				gap = i == n ? a[n - 1] : rmx[i + 1];
			} else {
				if (gap < a[i]) {
					gap = a[i];
				}
				drop += a[i] + dep[i] - gap;
			}
		}
		
		cout << ans << '\n';
	}
	
	return 0;
}