#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define veci vector<int> #define ll long long using namespace std; const int N=1e5+10,INF=1e9+10; struct dit{ int ls,rs,fa,sz; }T[N];int rt; int a[N];//BST-HEAP int n; void bd(){ stack<int> s;while(!s.empty()) s.pop(); for(int i=1;i<=n+1;i++){ int la=0;T[i]=(dit){0,0,0,0}; while(!s.empty()){ if(a[s.top()]<a[i]){ la=s.top();s.pop(); }else{ break; } }//cout<<la<<' '<<a[i]<<' '<<a[la]; if(!s.empty()){ T[s.top()].rs=i; T[i].fa=s.top(); }else{ rt=i; }if(la!=0){ T[la].fa=i; T[i].ls=la; }s.push(i); } }veci tt[N*2];int sz[N]; void dfs(int u){ if(!u) return ; sz[u]=1; //if(T[u].ls){ //cout<<'('; dfs(T[u].ls); //cout<<')';} //cout<<u; //if(T[u].rs){ //cout<<'('; dfs(T[u].rs); //cout<<')';} sz[u]+=sz[T[u].ls]+sz[T[u].rs]; if(u!=rt){ tt[sz[u]].push_back(u); } } #define go(i,j) for(int i=1;i<=n+1;i++) for(auto j:tt[i]) void slv(){ cin>>n;for(int i=1;i<=n;i++) cin>>a[i];a[n+1]=INF; for(int i=1;i<=n+1;i++) tt[i].clear(); bd();dfs(rt);//cout<<' '; ll now=0;ll ans=0; a[0]=INF; for(int i=1;i<=n+1;i++) now+=llabs(a[i]-a[i-1]); for(int i=1;i<=n;i++) ans+=a[i]; //cout<<now<<' '; go(i,j){ //cout<<j<<' '; ll cnt=a[T[j].fa]-a[j]; if(now-cnt*2<=INF*2){ ll k=(now-2*INF+1)/2; now-=2*k;ans+=sz[j]*k; }else{ now-=cnt*2;ans+=cnt*sz[j]; } }cout<<ans<<endl; } int main(){ //double c=clock(); int t;cin>>t;while(t--) slv(); //cerr<<(clock()-c)/CLOCKS_PER_SEC<<endl; return 0; }