#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, sum = 0;   cin>>n;
      vector<ll> Mex(n), v(n), pre(n);   cin(v);
      ll Min = n, Max = n-1;
      for(int i = n-1; i >-1; i--){
         Mex[i] = Min;
         Min = min(Min, v[i]);
         sum += Mex[i];
      }
      int p = 0;
      for(int i = 0; i<n; i++){
          p += Mex[i];
          pre[i] = p;
      }
      ll final_res = sum, j = n-1, pos = n;
      Max = min(Max, v[0]);
      for(int i = 1; i < n; i++){
        if(pos > -1)
        pos = lower_bound(all(Mex), Max) - Mex.begin();
        else pos = 0;
        if(Mex[pos]>= Max) pos--;
        if(pos == -1) sum = 0;
        else sum = pre[pos];
        final_res += ((n - (pos+1)) *  Max) + sum;
        Max = min(Max, v[i]);
      }
       cout<<final_res<<"\n";
    }
}