#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int n;
lld arr[2000000];
int nxt[2000000];
int prv[2000000];
map<lld,int> m;
set<lld> s;
lld sm(lld x, lld y){
    lld ans=(y-x+1);
    ans*=(x+y);
    ans/=2;
    return ans;
}
vector<lld >V;
const int MX=1'000'000;
class ST{
    lld mn[MX*4];
    public:
    void build(int a, int b, int node){
        mn[node]=0;
        if(a==b)return;
        int mid=(a+b)/2;
        build(a,mid,2*node);
        build(mid+1,b,2*node+1);
    }
    void update(int a, int b, int node, int pos, lld val){
        if(pos<a || b<pos)return;
        if(a==b){
            mn[node]=val;
            return;
        }
        int mid=(a+b)/2;
        update(a,mid,2*node,pos,val);
        update(mid+1,b,2*node+1,pos,val);
        mn[node]=min(mn[2*node],mn[2*node+1]);
    }
    lld query(int a, int b, int node, int l, int r){
        if(r<a || b<l)return 1e18;
        if(l<=a && b<=r)return mn[node];
        int mid=(a+b)/2;
        return min(query(a,mid,2*node,l,r),query(mid+1,b,2*node+1,l,r));
    }
};
ST S1,S2;
void solve(){
    m.clear();
    s.clear();
    cin>>n;
    rep(i,0,n)cin>>arr[i];
    rep(i,0,n)V.push_back(arr[i]);
    sort(V.begin(),V.end());
    V.resize(unique(V.begin(),V.end())-V.begin());
    int M=V.size();
    S1.build(0,M-1,1);
    S2.build(0,M-1,1);
    for(int i=n-1;i>-1;i--){
        if(m.find(arr[i])==m.end())nxt[i]=n;
        else nxt[i]=m[arr[i]];
        m[arr[i]]=i;
    }
    m.clear();
    rep(i,0,n){
        if(m.find(arr[i])==m.end())prv[i]=-1;
        else prv[i]=m[arr[i]];
        m[arr[i]]=i;
    }
    trav(a,m){
        lld X=a.second;
        S1.update(0,M-1,1,lower_bound(V.begin(),V.end(),a.first)-V.begin(),-(X*(X+1))/2-a.first);
        S2.update(0,M-1,1,lower_bound(V.begin(),V.end(),a.first)-V.begin(),-(X*(X+1))/2+a.first);
    }
    lld best=0;
    rep(i,0,n){
        S1.update(0,M-1,1,lower_bound(V.begin(),V.end(),arr[i])-V.begin(),1e18);
        S2.update(0,M-1,1,lower_bound(V.begin(),V.end(),arr[i])-V.begin(),1e18);
        if(prv[i]==-1){
            if((int)s.size()>0){
                set<lld>::iterator it=s.lower_bound(arr[i]);
                if(it!=s.end()){
                    best=min(best,*it-arr[i]-sm(i+1,nxt[i]));
                }
                if(it!=s.begin()){
                    best=min(best,arr[i]-*prev(it)-sm(i+1,nxt[i]));
                }
            }
            //~ best=min(best,S1.query(0,M-1,1,0,lower_bound(V.begin(),V.end(),arr[i])-V.begin())+arr[i]);
            //~ best=min(best,S2.query(0,M-1,1,lower_bound(V.begin(),V.end(),arr[i])-V.begin(),M-1)-arr[i]);
        }
        s.insert(arr[i]);
    }
    s.clear();
    lld ans=0;
    rep(i,0,n){
        s.insert(arr[i]);
        lld can=i+1;
        can*=s.size();
        ans+=can;
    }
    cout<<ans+best<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	cin>>tt;
	while(tt--){
		solve();
	}
}