#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define INF INT_MAX
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define nl "\n"
using namespace std;
const ll MOD  = 1e9+7;
const int mxN = 2e5+1;

int main()
{
    FAST
    //==================
    ll t = 1 ;
    cin >> t;
    while(t--){
        ll n; cin >> n;
        ll a[n] ;
        set<int> s;
        for(int i=0; i<=n;i++)s.insert(i);
        map<int,int> m ;
        int pos = -1 ;
        ll ans[n];
        for(int i=0;i<n;i++){
            cin >> a[i];
            if(a[i] == 0)pos = i;
            m[a[i]] = i;
        }
        ll fin =0 ;
        for(int i=pos;i<n;i++){
            s.erase(s.find(a[i]));
            fin+= *s.begin();
            ans[i] = fin;
        }
        for(int i=pos-1;i>=0;i--){
            if(m[a[i]-1]>pos){
                fin+= ans[m[a[i]-1]];
                s.erase(s.begin());
                fin+=(*s.begin());
            }else{
                fin+= ans[n-1];
                s.erase(s.find(a[i]));
            }
        }
        cout << fin << nl;

    }

}