#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define EPS 1e-6
#define Ceil(n, m) ((n / m) + ( n % m ? 1 : 0))
#define mod 1000000007
#define over 1e18
#define cin(v) for(auto &i: v)  cin>>i
#define cout(v) for(auto &i: v) cout<<i<<" ";
#define all(v) v.begin(), v.end()
#define LSB(n) (n & -n)
#define OO 2'000'000'000
void fcode(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
   /* #ifndef ONLINE_JUDGE
      freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) ,  freopen("error.txt", "w", stderr);
    #endif*/
}

int main(){
    fcode();
    ll t;    cin>>t;
    while(t--){
      ll n, zero_pos = -1, Min = 0, sum = 0, Max = -1;   cin>>n;
      vector<ll>exist(1e5+2), res(n), v(n);
      for(int i = 0; i<n; i++){
        cin>>v[i];
        exist[v[i]] = true;
        while(exist[Min])
          Min++;
        res[i] = Min;
        sum += Min;
        Max = max(Max, v[i]);
      }
      ll final_res = sum;
      int j = n-1;
      Max = min(Max, v[0]);
      for(int i = 1; i < n; i++){
        while(Max <= res[j] && j >-1){
          sum -= res[j];
          j--;
        }
        final_res += ((n - (j+1)) *  Max) + sum;;
        Max = min(Max, v[i]);
      }
      cout<<final_res<<"\n";
    }
}