#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)

#define pb push_back
#define eb emplace_back
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())

template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;

using vi=vc<int>;

template<class t,class u>bool chmin(t&a,u b){
	if(a>b){a=b;return true;}
	else return false;
}
template<class t,class u>bool chmax(t&a,u b){
	if(a<b){a=b;return true;}
	else return false;
}

#define mp make_pair
#define a first
#define b second
using pi=pair<int,int>;

const int inf=INT_MAX/2-100;

struct segtree{
	struct N{
		pi mn=pi(inf,-1),rw=pi(inf,-1);
		int lz=inf;
		void init(int v,int i){
			mn=pi(inf,-1);
			rw=pi(v,i);
			lz=inf;
		}
		void add(int v){
			chmin(mn,pi(rw.a+v,rw.b));
			chmin(lz,v);
		}
		void push(N&x,N&y){
			x.add(lz);
			y.add(lz);
			lz=inf;
		}
		static N merge(const N&x,const N&y){
			N res;
			res.mn=min(x.mn,y.mn);
			res.rw=min(x.rw,y.rw);
			res.lz=inf;
			return res;
		}
	};
	vc<N> x;
	int s,h;
	void upd(int i){
		//cerr<<"upd "<<i<<endl;
		x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	void push(int i){
		//cerr<<"push "<<i<<endl;
		x[i].push(x[i*2],x[i*2+1]);
	}
	void init(vi a){
		int n=si(a);
		s=1,h=0;while(s<n){s*=2;h++;}
		x.resize(s*2);
		rep(i,n)x[s+i].init(a[i],i);
		gnr(i,1,s)upd(i);
	}
	segtree(vi a){init(a);}
	/*void add(int i,int l,int r,int b,int e,int v){
		if(e<=l||r<=b)return;
		if(b<=l&&r<=e)return x[i].add(v);
		push(i);
		add(i*2,l,(l+r)/2,b,e,v);
		add(i*2+1,(l+r)/2,r,b,e,v);
		upd(i);
	}
	void add(int b,int e,int v){
		add(1,0,s,b,e,v);
	}*/
	void add(int b,int e,int v){
		//cerr<<"add "<<b<<" "<<e<<" "<<v<<endl;
		assert(b<=e);
		if(b==e)return;
		rep(k,h)push((b+s)>>(h-k));
		rep(k,h)push((e-1+s)>>(h-k));
		for(int l=b+s,r=e+s;l<r;l>>=1,r>>=1){
			if(l&1){
				//cerr<<"L "<<l<<endl;
				x[l].add(v);
				l++;
			}
			if(r&1){
				r--;
				x[r].add(v);
				//cerr<<"R "<<r<<endl;
			}
		}
		int lh=b==0?h:__builtin_ctz(b);
		int rh=__builtin_ctz(e);
		per(k,h-lh)upd((b+s)>>(h-k));
		per(k,h-rh)upd((e-1+s)>>(h-k));
	}
	void del(int i){
		assert(0<=i);
		i+=s;
		rep(k,h)push(i>>(h-k));
		x[i].init(inf,-1);
		while(i>>=1)upd(i);
	}
	/*pi get(int i,int l,int r,int b,int e){
		if(e<=l||r<=b)return pi(inf,-1);
		if(b<=l&&r<=e)return x[i].mn;
		return min(
			get(i*2,l,(l+r)/2,b,e),
			get(i*2+1,(l+r)/2,r,b,e));
	}
	pi get(int b,int e){
		return get(1,0,s,b,e);
	}*/
};

void slv(){
	int n;cin>>n;
	vi x(n);rep(i,n)cin>>x[i];
	vi neg=x;for(auto&v:neg)v=-v;
	
	segtree a(x),b(neg);
	
	//cerr<<"start"<<endl;
	
	ll ans=0;
	auto work=[&](int i){
		a.add(i+1,n,-x[i]);
		b.add(0,i,x[i]);
		a.del(i);
		b.del(i);
	};
	
	work(0);
	rep(step,n-1){
		pi cur=min(a.x[1].mn,b.x[1].mn);
		//cerr<<step<<" "<<cur.a<<" "<<cur.b<<endl;
		ans+=cur.a;
		work(cur.b);
	}
	
	cout<<ans<<endl;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	int t;cin>>t;rep(_,t)
	slv();
}