#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;

#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { x = 0; char GC; bool f = 0;
	for (; !IC; GC) f |= c == '-';
	for (; IC; GC) x = x * 10 + c - 48;
	if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) { meow("AF@%d\n", __LINE__ ); exit(v); }

#define vc vector
#define eb emplace_back
#define pb push_back

const int N = 1000006;
const ll inf = 1e13;
int n; ll a[N];

int ch[N][2];
vc<tuple<int, ll, int, int>> op;
void dfs(int u, int l, int r, ll pre) {
	op.eb(r - l - 1, pre - a[u], l, r);
	if (ch[u][0])
		dfs(ch[u][0], l, u, a[u]);
	while (a[ch[u][1]] == a[u]) {
		int v = ch[u][1];
		if (ch[v][0])
			dfs(ch[v][0], u, v, a[u]);
		u = v;
	}
	if (ch[u][1])
		dfs(ch[u][1], u, r, a[u]);
}

void solve() {
	rd(n);
	U (i, 1, n) rd(a[i]);
	a[0] = a[n + 1] = inf;
	int stk[n + 5], sp = 0; ms(stk, -1);
	U (i, 1, n) {
		while (sp && a[i] > a[stk[sp]]) --sp;
		if (stk[sp + 1] != -1)
			ch[i][0] = stk[sp + 1];
		if (sp)
			ch[stk[sp]][1] = i;
		stk[++sp] = i;
		stk[sp + 1] = -1;
	}
	int rt = stk[1];
	dfs(rt, 0, n + 1, inf);
	
	ll cur = 0, m = inf * 2;
	U (i, 1, n + 1) cur += abs(a[i] - a[i - 1]);
	sort(op.begin(), op.end());
	
	ll d[n + 2] {};
	for (auto [len, cnt, l, r] : op) {
		if (cur < m)
			break;
		if (cur - cnt * 2 <= m) {
			d[l + 1] += (cur - m) / 2;
			d[r] -= (cur - m) / 2;
			cur = m;
			break;
		} else {
			d[l + 1] += cnt;
			d[r] -= cnt;
			cur -= cnt * 2;
		}
	}
	
	ll ans = 0;
	U (i, 1, n) d[i] += d[i - 1], ans += d[i] + a[i];
	
	printf("%lld\n", ans);
}

void clear() {
	U (i, 0, n) ms(ch[i], 0);
	op.clear();
}

int main() {
//	freopen("ava.in", "r", stdin);
	
	int T; rd(T);
	while (T--) {
		solve();
		clear();
	}
}