//#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
  
void Fast()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
void File() {
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
}
typedef long long ll;
void justify(int n,int x)
{
    string s=to_string(n);
    for(int i=0;i<x-s.size();i++)cout<<' ';
    cout<<s;
}
void solve()
{
    int n,x=0;
    ll res=0,c=0;
    cin>>n;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    vector<int>a(n);
    pair<int,int>p;
    vector<bool> mex_l(n+1),mex_r(n+1);
    c=n+1;
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
        p={a[i],i+1};
        pq.push(p);
        mex_l[a[i]]=1;
        
        while (mex_l[x])
        {
            p=pq.top();
            c=min(c,0ll+p.second);
            pq.pop();
            x++;
        }
        res+=c*x;
    }
    x=0;
    c=n+1;
    while (pq.size())
    {
        pq.pop();
    }
    
    for (int i = n-1; i >= 0; i--)
    {
        p={a[i],n-i};
        pq.push(p);
        mex_r[a[i]]=1;
        
        while (mex_r[x])
        {
            p=pq.top();
            c=min(c,0ll+p.second);
            pq.pop();
            x++;
        }
        res+=c*x;
    }
    cout<<res-n<<'\n';
}
int main()
{
    File();
    Fast();
    
    int t=1;
    cin>>t;
    for (int i = 1; i <= t;i++ )
    {
        //cout<<"Case #"<<i<<": ";
        solve();
    }

}