#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <stdio.h>
#define ll long long
#define mem(a,n) memset((a),n,sizeof (a))
void fast();
ll gcd(ll x, ll y) { return(!y ? x : gcd(y, x % y)); }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
int dx[]{ 1, -1, 0, 0, 1, 1, -1, -1 };
int dy[]{ 0, 0, 1, -1, 1, -1, 1, -1 };
using namespace std;
vector<ll>mnb;
int search(int s, int e, ll tar) {
    int ans = -1; int mid;
    while (s <= e) {
        mid = (s + e) / 2;
        if (mnb[mid] > tar) {
            ans = mid;
            e = mid - 1;
        }
        else s = mid + 1;
    }
    return ans;
}
int main()
{
    //freopen("input.txt" ,"r" ,stdin);
   //freopen("output.txt" ,"w" ,stdout);
    fast();
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<ll>v(n);
        for (int i = 0; i < n; i++)cin >> v[i];
        vector<ll>mnb2(n+5);
        mnb = vector<ll>(n+5);
        mnb[n - 1] = n; mnb2[n - 1] = n;
        ll mn = min((ll)n, v[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            mnb[i] = mn; mnb2[i] = mnb[i];
            mnb2[i] += mnb2[i + 1];
            mn = min(mn, v[i]);
        }
        
        //for (auto it : mnb)cout << it << " ";
        //cout << endl;
        //for (auto it : mnb2)cout << it << " ";
        //cout << endl;
        mn = n; ll ans = 0;
        for (int i = 0; i < n; i++) {
            int indx = search(i, n - 1, mn);
            if (indx == -1) {
                ans += mnb2[i];
            }
            else {
                ans += mnb2[i] - mnb2[indx];
                ans += (n-indx) * mn;
            }
            mn = min(mn, v[i]);
        }
        cout << ans << "\n";
    }
   


    return 0;
}
void fast() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}