#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];
void solv() {
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    ll ans = 0;
    set<int> st;
    for(int i = 1;i <= n;i++) {
        st.insert(a[i]) ;
        ans += 1LL * i * st.size() ;
    }


    map<int,vector<int> > mp;
    vector<int> v;
    for(int i = 1 ; i <= n;i++) mp[a[i]].push_back(i) , v.push_back(a[i]);
    sort(v.begin() , v.end()) ;
    v.erase(unique(v.begin() , v.end()) , v.end()) ;

    vector<pii> p;
    for(auto &[x,y] : mp) p.push_back({y[0] , x}) ;

    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 = mp[p[i].second] ;
        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 &v = mp[p[i].second] ;
        int b2 , b1 = p[i].first; 
        if(v.size() == 1) b2 = n + 1;
        else b2 = v[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)) ;
        b[0].upd(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() ;
}