#include <bits/stdc++.h>
 
using namespace std;
template<typename T> void umax(T &a, const T b) {a = max(a, b);}
template<typename T> void umin(T &a, const T b) {a = min(a, b);}
 
int main() {
  cin.tie(0)->sync_with_stdio(false);
  int T; cin >> T;
  while (T--) {
    int N; cin >> N;
    vector<int> A(N); for (auto &a : A) cin >> a;
    int l = 0, r = N-1;
    set<int> avL, avR;
    int mxL = 0, mxR = 0;
    set<int>::iterator it;
    int64_t ans = 0;
    while (l < r) {
      if (A[r] <= mxR && (it = avR.upper_bound(A[r])) == avR.begin()) {
        r--;
        continue;
      }
      for (int i = mxR+1; i <= A[r]; ++i) avR.insert(i);
      umax(mxR, A[r]);
      it = prev(avR.upper_bound(A[r]));
      avR.erase(it);
      while (l < r) {
        if (A[l] <= mxL && (it = avL.upper_bound(A[l])) == avL.begin()) {
          l++;
          continue;
        }
        for (int i = mxL+1; i <= A[l]; ++i) avL.insert(i);
        umax(mxL, A[l]);
        it = prev(avL.upper_bound(A[l]));
        avL.erase(it);
        break;
      }
      if (l >= r) break;
      ans += r - l;
      r--;
      l++;
    }
    cout << ans << '\n';
  }
  return 0;
}