#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=1e5+10; struct nd { int ls,rs,siz; }d[maxn]; int n,stk[maxn],fa[maxn],tp;ll a[maxn]; void dfs(int u){ d[u].siz=1; if(d[u].ls)dfs(d[u].ls),d[u].siz+=d[d[u].ls].siz; if(d[u].rs)dfs(d[u].rs),d[u].siz+=d[d[u].rs].siz; } void slv(){ n=read();up(i,1,n)a[i]=read(); up(i,1,n)d[i].ls=d[i].rs=d[i].siz=fa[i]=0;tp=0; up(i,1,n){ int lst=-1; while(tp&&a[stk[tp]]<=a[i])lst=stk[tp--]; if(lst!=-1)d[i].ls=lst; if(tp)d[stk[tp]].rs=i; stk[++tp]=i; }up(i,1,n)fa[d[i].ls]=fa[d[i].rs]=i; int rt=0;up(i,1,n)if(!fa[i])rt=i; dfs(rt);ll sum=0,inf=1e12; a[0]=a[n+1]=inf;up(i,1,n+1)sum+=abs(a[i]-a[i-1]); ll res=0;up(i,1,n)res+=a[i]; vector<pi>vec; up(i,1,n)if(fa[i])vec.p_b(m_p(d[i].siz,a[fa[i]]-a[i])); sort(vec.begin(),vec.end());int p=0; while(sum>2*inf){ ll need=min((ll)vec[p].p2,(sum-2*inf+1)/2); res+=need*vec[p].p1,sum-=need*2;p++; }printf("%lld\n",res); } int main(){ //freopen("1.in","r",stdin),freopen("1.out","w",stdout); int t=read();while(t--)slv(); return 0; }