#include<bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
//#define int long long
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLL;
int lowbit(int x) {return x & (- x);};
const int N = 200010, mod = 998244353;
const int Mod = 1e9 + 7, INF = 0x3f3f3f3f;

void solve(){
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    priority_queue<PLL, vector<PLL>, greater<PLL>> q;
    vector<ll> val(n + 1), siz(n + 1);
    vector<ll> pre(n + 1), nxt(n + 1);
    vector<int> vis(n + 1);
    for(int i = 1; i <= n; i ++){
        pre[i] = i - 1;
        nxt[i] = i + 1;
        siz[i] = 1;
        val[i] = a[i];
        q.push({a[i], i});
    }
    ll ans = 0;
    auto merge =[&](ll x, ll y, ll lei) -> void{
        ll cha = val[y] - val[x];
        ans += cha * siz[x];
        siz[x] += siz[y];
        val[x] = val[y];
        if(lei == 1){
            pre[x] = pre[y];
        }
        else{
            nxt[x] = nxt[y];
        }
        q.push({val[x], x});
        vis[y] = 1;
    };
    while(q.size() >= 2){
        auto [v1, i] = q.top();
        q.pop();
        if(vis[i]) continue;
        ll pp = pre[i], nn = nxt[i];
        if(pp == 0 && nn == n + 1) break;
        if(pp == 0){
            merge(i, nn, 2);
        }
        else if(nn == n + 1){
            merge(i, pp, 1);
        }
        else{
            ll vl1 = val[pp], vl2 = val[nn];
            if(vl1 <= vl2) merge(i, pp, 1);
            else merge(i, nn, 2);
        }
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}