/*
+---------------------------------------------+
|                                             |
|  Copytright, MinaMagdy, 23/04/2022 (14:34)  |
|                                             |
+---------------------------------------------+
*/
/*
        .@@@@@@@@   @@@                                              @@       @@
    ,@@@@@@     @@ .@@@      @@    @@@        @@@%@@@@.   @@@        @@  @@  @@@@/      @@@
    /& @@@@    @@@ *@@@     @@@#  @@@&@@@    @@@@@@@#&@@ @@@%&,      @@ @@@@  @@@@    @@@&
        @@@  .@@@   /@%@     @@@  @@@@   @@& .@@@         @@&&&@      @@ @@@@  >@@@@ @@@@
        %@@@@@@&     /&&&     %@&  @&@     @& @&@&         &&@#%@%.   &@@ &@&#   %@@@@@@
        @@@@@        /@&%@%&@@@&@  @&&    ,@@ @@&&@@&@@@   &@@ /@@&/  @@, @@@/    %@@@@
        @@@.         *@@@@#,  @@@  @@@   ,@@  @@@.         @@@   @@@@@@@  %@@/   @@@@@@%
        @@@          *@@%     @@@   @@@@@@#    @@@@@@@@@@  @@@    ,@@@@    @@& .@@@  @@@@
        &@@,          @@%      @@                          @@@                 @@      @@@
                                                            &*
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

using namespace __gnu_cxx;
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ceil(w, m) (((w) / (m)) + ((w) % (m) ? 1 : 0))
#define endl "\n"
#define NumOfDig(w) log10(w) + 1
#define MOD 1000000007
#define INF 2000000000
#define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
#define EPS 1e-9
#define PI1 acos(-1)
#define PI2 3.141592653
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define sz(x) int(x.size())
#define init(x, c) memset(x, c, sizeof(x))
#define getlineCh(s, c) getline(cin >> ws, s, c)
#define TC int testcases = 1; cin >> testcases; for (ll test = 1; test <= testcases; test++)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

/**
 * @author MiinaMagdy
 * @remark Time limit - memory limit (EFFICIENCY)
 * @remark (OVERFLOW) long long
 * @remark freopen() file
 * @remark (CORNER) test case
 * @remark division by (ZERO) || Out of array's (RANGE)
 * @remark use logarithm if you want to compare two products
 * @remark Brute Force means try all possible solutions remember (MAXPOINT - CodeChef)
 * @remark '/0' takes all input in getline string
 */

void phoenix()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
    #endif
    Time
}

int main(void)
{
    phoenix();
    int testcase = 1;
    cin >> testcase;
    while (testcase--)
    {
        ll n;
        cin >> n;
        ll arr[n];
        map<ll, ll> idx;
        for (int i = 0; i < n; i++) cin >> arr[i], idx[arr[i]] = i;
        ll l = idx[0], r = idx[0];
        ll vis[n + 5]{};
        ll Mex = 1, ans = 0;
        while (Mex < n) {
            ll low, high;
            if (idx[Mex] > idx[Mex - 1]) {
                low = 0, high = idx[Mex] - 1;
                ll left = abs(low - l) + 1, right = abs(high - r) + 1;
                ans += (left * right) * Mex;
                while (r < n and arr[r] != Mex) {
                    vis[arr[r]] = 1;
                    r++;
                }
                if (r < n) vis[arr[r]] = 1;
            }
            else {
                low = idx[Mex] + 1, high = n - 1;
                ll left = abs(low - l) + 1, right = abs(high - r) + 1;
                ans += (left * right) * Mex;
                while (l >= 0 and arr[l] != Mex) {
                    vis[arr[l]] = 1;
                    l--;
                }
                if (l >= 0) vis[arr[l]] = 1;
            }
            while (vis[Mex]) Mex++;
        }
        cout << ans + n << endl;
    }
    return 0;
}