#include<bits/stdc++.h>
using namespace std;
constexpr int M=1e6+5,inf=0x3f3f3f3f;
int n,a[M],ls[M],rs[M],stk[M];
long long tmp,ans,buc[M];
int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
void dfs(int p,int l,int r,int lst){
    if (!~p) return;
    buc[r-l+1]+=lst-a[p];
    dfs(ls[p],l,p-1,a[p]);
    dfs(rs[p],p+1,r,a[p]);
}
void solve(){ n=read();
    a[0]=a[n+1]=inf;ans=tmp=0;
    for (int i=1;i<=n;i++) ans+=a[i]=read();
    for (int i=0;i<=n;i++) tmp+=abs(a[i]-a[i+1]);
    if ((tmp-=inf*2)<=0) return printf("%lld\n",ans),void();
    for (int i=1;i<=n;i++) buc[i]=0;
    for (int i=0,tp=0;i<=n+1;i++){
        int cur=tp;ls[i]=rs[i]=-1;
        while (cur&&a[stk[cur]]<a[i]) cur--;
        if (cur) rs[stk[cur]]=i;
        if (cur<tp) ls[i]=stk[cur+1];
        stk[tp=cur+1]=i;
    }
    dfs(stk[1],0,n+1,inf);tmp=tmp+1>>1;
    for (int i=1;i<=n;i++){
        long long need=min(buc[i],tmp);
        ans+=need*i;tmp-=need;
    }
    printf("%lld\n",ans);
}
int main(){int T=read();while (T--) solve();return 0;}