Untitled

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define int long long
using namespace std;

const int MAXN = 5e5 + 5;
int n;
int a[MAXN], mn[MAXN], mx[MAXN], cnt[MAXN * 2];

int dc(int l, int r) {
    if (l == r) return 1;
    int mid = (l + r) / 2;
    int res = dc(l, mid) + dc(mid + 1, r);
    mn[mid + 1] = mx[mid + 1] = a[mid + 1];
    for (int i = mid + 2; i <= r; i++) {
        mn[i] = min(mn[i - 1], a[i]);
        mx[i] = max(mx[i - 1], a[i]);
    }
    mn[mid] = mx[mid] = a[mid];
    for (int i = mid - 1; i >= l; i--) {
        mn[i] = min(mn[i + 1], a[i]);
        mx[i] = max(mx[i + 1], a[i]);
    }
    // min in left, max in left
    for (int i = mid; i >= l; i--) {
        int R = l + mx[i] - mn[i];
        if (R > mid and R <= r and mx[R] < mx[i] and mn[R] > mn[i]) res++;
    }
    // min in right, max in right
    for (int i = mid + 1; i <= r; i++) {
        int L = r + mn[i] - mx[i];
        if (L >= l and L <= mid and mx[L] < mx[i] and mn[L] > mn[i]) res++;
    }
    // max in left, min in right
    for (int i = mid, R = mid + 1, rr = mid + 1; i >= l; i--) {
        while (R <= r and mx[R] < mx[i]) cnt[R + mn[R]]++, R++;
        while (rr < R and mn[rr] > mn[i]) cnt[rr + mn[rr]]--, rr++;
        res += cnt[i + mx[i]];
    }
    // init
    for (int i = mid + 1; i <= r; i++) cnt[i + mx[i]] = 0;
    // max in right, min in left
    for (int i = mid, R = mid + 1, rr = mid + 1; i >= l; i--) {
        while (R <= r and mn[R] > mn[i]) cnt[n - R + mx[R]]++, R++;
        while (rr < R and mx[rr] < mx[i]) cnt[n - rr + mx[rr]]--, rr++;
        res += cnt[n - i + mn[i]];
    }
    // init
    for (int i = mid + 1; i <= r; i++) cnt[n - i + mn[i]] = 0;
    return res;
}

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << dc(1, n) << '\n';
}

signed main() {
    int t; cin >> t;
    while (t--) solve();
}