#pragma GCC optimize("Ofast", "O3", "inline", "unroll-loops")
#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int ch = 0, f = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
#define fi first
#define se second
inline void solve(){
    int n; read(n);
    vector<int> a(n + 1), fa(n + 1);
    for(int i = 1; i <= n; i++) read(a[i]), fa[i] = i;
    auto ask = [&](auto &ask, int x) -> int {
        return x == fa[x] ? x : fa[x] = ask(ask, fa[x]);
    };
    ll ans = 0;
    while(1){
        int cnt = 0;
        for(int i = 1; i <= n; i++) if(ask(ask, i) == i) cnt++;
        if(cnt == 1) break;
        pair<pair<int, int>, pair<int, int> >  pre = {{-1, -1}, {-1, -1}}, suf = {{-1, -1}, {-1, -1}};
        auto update = [&](int x, int c, pair<pair<int, int>, pair<int, int> > &pii) -> void {
            auto &[vfi, vse] = pii;
            if(x < vfi.fi || vfi.se == -1){
                if(c != vfi.se) vse = vfi, vfi = {x, c};
                else vfi = {x, c};
            }
            else if((x < vse.fi || vse.se == -1) && c != vfi.se) vse = {x, c};
        };
        auto fetch = [&](int x, int c, pair<pair<int, int>, pair<int, int> > &pii) -> pair<int, int> {
            auto [vfi, vse] = pii;
            if(vfi.se == -1) return {-1, -1};
            if(vfi.se != c) return {x + vfi.fi, vfi.se};
            if(vse.se == -1 || vse.se == c) return {-1, -1};
            return {x + vse.fi, vse.se};
        };
        vector<pair<int, int> > out(n + 1, {-1, -1});
        for(int i = 1; i <= n; i++){
            auto [w, j] = fetch(a[i], fa[i], pre);
            // cout << w << endl;
            if(j != -1 && (w < out[fa[i]].fi || out[fa[i]].se == -1)) out[fa[i]] = {w, j};
            update(-a[i], fa[i], pre);
        }
        for(int i = n; i >= 1; i--){
            auto [w, j] = fetch(-a[i], fa[i], suf);
            if(j != -1 && (w < out[fa[i]].fi || out[fa[i]].se == -1)) out[fa[i]] = {w, j};
            update(a[i], fa[i], suf);
        }
        for(int i = 1; i <= n; i++) if(fa[i] == i){
            assert(~out[i].se);
            // cout << i << " " << out[i].se << " " << out[i].fi << endl;
            int p = ask(ask, i), q = ask(ask, out[i].se);
            if(p == q) continue;
            ans += out[i].fi;
            fa[p] = q;
        }
    }
    printf("%lld\n", ans);
}
int main(){
    int T; read(T);
    while(T--) solve();
    return 0;
}