#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=100010,N=12,V=10,inf=100000000000; int n,sum,num,ans,a[MAXN],l[MAXN],r[MAXN],siz[MAXN]; stack<int>st; priority_queue<pii>q; void dfs(int u,int lst){ if(l[u])dfs(l[u],u); if(r[u])dfs(r[u],u); siz[u]=siz[l[u]]+siz[r[u]]+1; q.push(mk(-siz[u],a[lst]-a[u])); } void slv(){ n=read(); a[0]=a[n+1]=inf;ans=num=sum=0; for(int i=1;i<=n;i++)num+=a[i]=read(),l[i]=r[i]=0; for(int i=0;i<=n;i++)sum+=abs(a[i]-a[i+1]); for(int i=1;i<=n;i++){ while(!st.empty()&&a[st.top()]<a[i])l[i]=st.top(),st.pop(); if(!st.empty())r[st.top()]=i; st.push(i); } while(st.size()>1)st.pop(); dfs(st.top(),0);st.pop(); while(sum>inf*2){ pii now=q.top();q.pop(); int tmp=min(sum-inf*2,now.sc*2); sum-=tmp;ans+=tmp/2*-now.fr; } printf("%lld\n",ans+num); } signed main(){ int _=read();while(_--) slv(); return 0; }