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

ll T,n;
ll a[510000],b[510000],tr[510000],ans[510000];
ll sum,m;

void add(ll x,ll k){
    while (x<510000){
        tr[x]+=k;
        x+=(x&-x);
    }
}

ll query(ll x){
    ll res=0;
    while (x){
        res+=tr[x];
        x-=(x&-x);
    }
    return res;
}

int main(){
    freopen("Milk.in","r",stdin);
    freopen("Milk.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--){
        cin>>n;
        for (int i=1;i<=n;i++) ans[i]=tr[i]=0;
        for (int i=1;i<=n;i++){
            cin>>a[i];
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        m=unique(b+1,b+n+1)-b-1;
        for (int i=1;i<=n;i++){
            int x=lower_bound(b+1,b+m+1,a[i])-b;
            ans[i]=query(x-1);
            add(x,1);
        }
        for (int i=1;i<=n;i++) tr[i]=0;
        sum=0;
        for (int i=n;i;i--){
            int x=lower_bound(b+1,b+m+1,a[i])-b;
            sum+=min(ans[i],query(x-1));
            add(x,1);
        }
        cout<<sum<<'\n';
    }
    return 0;
}