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

#define cn getchar
template<class TY>void read(TY &x){
	x=0;int f1=1;char ch=cn();
	while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
template<class TY>void write2(TY x){
	if(x>9)write2(x/10);
	putchar(x%10+'0');
}
template<class TY>void write(TY x){
	if(x<0)putchar('-'),x=-x;
	write2(x);
}
struct Fenwick{
	vector<long long> tr;
	int n;
	Fenwick(int N){
		tr.resize(N+1,inf);
		n=N;
	}
	void change(int x,long long y){
		for(;x<=n;x+=(x&-x))
			tr[x]=min(tr[x],y);
	}
	long long query(int x){
		long long re=inf;
		for(;x;x-=(x&-x))
			re=min(re,tr[x]);
		return re;
	}
};

int main()
{
	int Te;read(Te);while(Te--){
		int n;read(n);
		vector<int> a(n+1),val(n+1);
		vector<pair<int,int>> b(n+1);
		b[0] = make_pair(0,0);
		for(int i=1;i<=n;i++)
			read(a[i]),b[i]=make_pair(a[i],i);
		sort(b.begin(),b.end());//将a离散化
		int cnt=0;
		for(int i=1;i<=n;i++)
			if(b[i].first!=b[i-1].first)
				a[b[i].second] = ++cnt, val[cnt] = b[i].first;
			else a[b[i].second] = cnt;
		
		vector<long long> del(n+1);//
		map<int,int> pos;
		for(int i=n;i>=1;i--){
			if(pos.find(a[i])==pos.end())
				del[i] = 1ll*(i+n) * (n+1-i)/2;
			else{
				del[i] = 1ll*(i+pos[a[i]]-1) * (pos[a[i]]-i)/2;
				del[pos[a[i]]] = 0;
			}
			pos[a[i]]=i;
		}
		// 从左往右，每次选差值最小的
		pos.clear();
		vector<int> c(n+1); int tot=0;
		set<int> s;
		long long sum=0, ans=inf;
		for(int i=1;i<=n;i++){
			c[a[i]]++;
			if(c[a[i]]==1)tot++;
			sum += 1ll*i*tot;
			if(i){
				auto j = s.lower_bound(a[i]);
				if(j!=s.end() && *j == a[i]);
				else{
					if(j != s.end())ans = min(ans, (long long)-del[i]+(val[*j]-val[a[i]]));
					if(j != s.begin()){
						j--;
						ans = min(ans, (long long)-del[i]+(val[a[i]]-val[*j]));
					}
				}
			}
			s.insert(a[i]);
		}
		if(tot == 1){
			write(sum);puts("");
			continue;
		}
		//从右往左
		// ans = inf;
		Fenwick tr1(n),tr2(n);
		for(int i=n;i>=1;i--){
			ans = min(ans, -del[i] + val[a[i]] + (i-1ll*i*i)/2 + tr1.query(a[i]-1));
			ans = min(ans, -del[i] + -val[a[i]] + (i-1ll*i*i)/2 + tr2.query(n-a[i]));
			tr1.change(a[i], -val[a[i]] + (1ll*i*i-i)/2);
			tr2.change(n-a[i]+1, val[a[i]] + (1ll*i*i-i)/2);
		}
		write(sum + ans);puts("");
	}
}
/*
3
4
1 2 3 4
4
1 2 3 4
4
1 2 3 4
*/