#include <bits/stdc++.h>
using namespace std;
int n ;
int a[1000005];
typedef long long ll;
typedef pair<int,int> pii;
ll S(int x) {
    return 1LL * x * (x + 1) / 2;
}
struct bit {
    ll c[1000005];
    int n;
    void init(int _n) {
        n = _n;
        for(int i = 1;i <= n;i++) c[i] = 1e18;
    }
    void upd(int x,ll y) {
        while(x <= n) {
            c[x] = min(c[x] , y);
            x += (x & -x);
        }
    }
    ll qry(int x) {
        ll ans = 1e18;
        while(x) {
            ans = min(ans , c[x]) ;
            x -= (x & -x);
        }
        return ans;
    }
}b[2];
mt19937 rnd(0);
vector<int> pos[1000005];
int ap[1000005];
void solv() {
    cin >> n;
    vector<int> v;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        // a[i] = rnd()%1000000000 + 1;
        v.push_back(a[i]) ;
    }
    sort(v.begin() , v.end()) ;
    v.erase(unique(v.begin() , v.end()) , v.end()) ;
    for(int i = 1;i <= v.size();i++) pos[i].clear() ;
    ll ans = 0;
    set<int> st;
    int cc = 0;
    for(int i = 1;i <= n;i++) {
        st.insert(a[i]) ;
        ap[i] = lower_bound(v.begin() , v.end() , a[i]) - v.begin() + 1;
        if(pos[ap[i]].size() == 0) cc++ ;
        pos[ap[i]].push_back(i) ;
        ans += 1LL * i * cc ;
    }



    vector<pii> p;
    for(int i = 1;i <= v.size() ; i++) {
        p.push_back({pos[i][0] , v[i - 1]}) ;
    }

    sort(p.begin() , p.end()) ;
    st.clear() ;
    ll sol = 0;
    auto qmin = [&](int x) ->ll {
        if(st.size() == 0) return 1e18;
        auto it = st.lower_bound(x) ;
        ll ans = 1e18;
        if(it != st.end())  ans = min(ans , (ll)abs(x - (*it))) ;
        if(it != st.begin()) {
            it-- ;
            ans = min(ans , (ll)abs(x - (*it))) ;
        }
        return ans;
    };
    for(int i = 0;i < p.size();i++) {
        auto &v = pos[ap[p[i].first]] ;
        int b2;
        if(v.size() == 1) b2 = n + 1;
        else b2 = v[1];
        ll dec = S(b2 - 1) - S(v[0] - 1) ;
        ll cur = qmin(p[i].second) - dec ;
        sol = min(sol , cur) ;
        st.insert(p[i].second) ;
    }

    b[0].init(v.size()) ; 
    b[1].init(v.size()) ;
    for(int i = p.size() - 1 ; i >= 0;i--) {
        auto &vt = pos[ap[p[i].first]] ;
        int b2 , b1 = p[i].first; 
        if(vt.size() == 1) b2 = n + 1;
        else b2 = vt[1];

        int bpos = lower_bound(v.begin() , v.end() , p[i].second) - v.begin() + 1;
        /// if a > b , a - b - S(b2-1) + S(a1)

        sol = min(sol , -S(b2 - 1) - p[i].second + b[0].qry(v.size() - bpos + 1)) ;
        // assert((int)v.size() - bpos + 1 > 0) ;
        // assert(bpos > 0);
        b[0].upd((int)v.size() - bpos + 1 , p[i].second + S(b1)) ;


        /// if a < b , b - a - S(b2-1) + S(a1)
        sol = min(sol , p[i].second - S(b2 - 1) + b[1].qry(bpos)) ;
        b[1].upd(bpos , -p[i].second + S(b1)) ;
    }
    cout << ans + sol << '\n' ;
    return ;
}
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    int t;cin >> t;
    while(t--) solv() ;
}