pattern

#include <cstdio>
typedef long long ll;
const int N = 500001, inf = 1e9;
struct Segtree {
    struct node {
        int mn, cnt;
        //node(int mn = 0, int cnt = 1) : mn(mn), cnt(cnt) {}
        friend node operator+(const node &a, const node &b) {
            if(a.mn != b.mn) return a.mn < b.mn ? a : b;
            return {a.mn, a.cnt+b.cnt};
        }
    } st[N<<1];
    int n, lz[N];
    void init(int _n) {
        n = _n;
        for(int i = 0; i < n; i++) st[i+n] = {inf, 1}, lz[i] = 0;
        for(int i = n-1; i > 0; i--) st[i] = st[i<<1]+st[i<<1|1];
    }
    void upd(int p, int d) {
        st[p].mn += d;
        if(p < n) lz[p] += d;
    }
    void pull(int p) {
        for(; p>1; p>>=1) {
            st[p>>1] = st[p]+st[p^1];
            st[p>>1].mn += lz[p>>1];
        }
    }
    void add(int l, int r, int d) {
        if(l == r) return;
        int L = l, R = r;
        for(l+=n,r+=n; l<r; l>>=1,r>>=1) {
            if(l&1) upd(l++, d);
            if(r&1) upd(--r, d);
        }
        pull(L+n), pull(R-1+n);
    }
} sgt;
int n, v[N], pos[N], d[N];
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", v+i);
    for(int i = 1; i <= n; i++) pos[--v[i]] = i;
    v[0] = v[n+1] = n;
    sgt.init(n);
    ll ans = 0;
    for(int i = n-1; i >= 0; i--) {
        int p = pos[i];
        int a = v[p-1]>i ? v[p-1] : n;
        int b = v[p+1]>i ? v[p+1] : n;
        sgt.add(i, n, -1);
        sgt.add(i, a, 1);
        sgt.add(i, b, 1);
        sgt.add(i, i+1, -inf);
        ans += sgt.st[1].cnt;
    }
    printf("%lld\n", ans);
}
signed main() {
    //ios_base::sync_with_stdio(0), cin.tie(0);
    int t;
    scanf("%d", &t);
    while(t--)
        solve();
}