#include<bits/stdc++.h>
using namespace std;
constexpr int N=3e5+5;
int n,a[N],fa[N],to[N],val[N],sb[N];
inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
inline void solve(){
    cin>>n;for(int i=1;i<=n;i++) cin>>a[i],fa[i]=i;
    int w=n-1;
    long long ans=0;
    while(w){
        pair<int,int> yanami(a[1],getfa(1)),nukumizu(-1e9,0);
        for(int i=1;i<=n;i++) val[i]=1e9,sb[i]=fa[i]==i;
        for(int i=2;i<=n;i++){
            int f=getfa(fa[i]);
            auto&cur=(f!=yanami.first?yanami:nukumizu);
            if(a[i]-cur.first<val[f])to[f]=cur.second,val[f]=a[i]-cur.first;
            nukumizu=max(nukumizu,cur);
            cur=max(cur,make_pair(a[i],f));
        }
        yanami=make_pair(a[n],getfa(n)),nukumizu=make_pair(1e9,0);
        for(int i=n-1;i>=1;i--){
            int f=getfa(fa[i]);
            auto&cur=(f!=yanami.first?yanami:nukumizu);
            if(cur.first-a[i]<val[f])to[f]=cur.second,val[f]=cur.first-a[i];
            nukumizu=min(nukumizu,cur);
            cur=min(cur,make_pair(a[i],f));
        }
        for(int i=1;i<=n;i++) if(sb[i]&&getfa(i)!=getfa(to[i])){
            fa[getfa(to[i])]=getfa(i);w--;
            ans+=val[i];
        }
    }
    cout<<ans<<'\n';
}
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
}