#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)

#pragma GCC optimize("-O3","unroll-loops")
#pragma GCC optimize("-Ofast")
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=2'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;
set<pair<lld,lld> > S;
void solve(){
    //~ V.clear();
    m.clear();
    s.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;
    }
    //~ 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);
    //~ }
    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;
    }
    
    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]));
                }
            }
            //~ lld I=nxt[i];
            //~ best=min(best,S1.query(0,M-1,1,0,lower_bound(V.begin(),V.end(),arr[i])-V.begin())+arr[i]-(I*(I+1))/2);
            //~ best=min(best,S2.query(0,M-1,1,lower_bound(V.begin(),V.end(),arr[i])-V.begin(),M-1)-arr[i]-(I*(I+1))/2);
        }
        s.insert(arr[i]);
    }
    
    for(int i=n-1;i>-1;i--){
        if(prv[i]==-1){
            lld I=i;
            auto it=S.insert({arr[i],(I*(I+1))/2-arr[i]}).first;
            lld I2=nxt[i];
            if(it!=S.begin())best=min(best,arr[i]-(I2*(I2+1))/2+prev(it)->second);
            while(it!=S.begin() && prev(it)->second>=it->second){
                S.erase(prev(it));
            }
        }
    }
    S.clear();
     for(int i=n-1;i>-1;i--){
        if(prv[i]==-1){
            lld I=i;
            auto it=S.insert({arr[i],(I*(I+1))/2+arr[i]}).first;
            lld I2=nxt[i];
            if(next(it)!=S.end()){
                best=min(best,-arr[i]-(I2*(I2+1))/2+next(it)->second);
            }
            while(next(it)!=S.end() && next(it)->second>=it->second){
                S.erase(next(it));
            }
        }
    }
    
    s.clear();
    lld ans=0;
    rep(i,0,n){
        s.insert(arr[i]);
        lld can=i+1;
        can*=s.size();
        ans+=can;
    }
    //cout<<ans<<endl;
    cout<<ans+best<<"\n";
}

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