/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> Merge(vector<ll>&v1,vector<ll>&v2)
{
    int n = v1.size(), m = v2.size();
    vector<ll> v(n+m);
    int a=0,b=0,c=0;
    while(a<n && b<m)
    {
        if(v1[a] < v2[b])
        {
            v[c] = v1[a];
            ++c;
            ++a;
        }
        else
        {
            v[c] = v2[b];
            ++b;
            ++c;
        }
    }
    while(a<n) {v[c] = v1[a] , ++c , ++a;}
    while(b<m) {v[c] = v2[b] , ++c , ++b; }
    return v;
}

void build(int node,int start,int end,vector<ll> &a,vector<vector<ll>> &sg)
{
    if(start == end)
    {
        sg[node].push_back(a[start]);
        return;
    }
    int mid = (start+end)/2;
    build(node*2,start,mid,a,sg);
    build(node*2+1,mid+1,end,a,sg);
    //merge(sg[node*2].begin(),sg[node*2].end(),sg[node*2+1].begin(),sg[node*2+1].end(),sg[node].begin());
    sg[node] = Merge(sg[node*2],sg[node*2+1]);
}

ll query1(int node,int start,int end,int l,int r,ll x,vector<ll>&v, vector<vector<ll>>&sg)
{
    if(l>end || r<start) return 0;
    if(l<=start && r>=end)
    {
        int lo = 0, hi = sg[node].size()-1,mid, ans=-1;
        while(lo<=hi)
        {
            mid = (lo+hi)/2;
            if(sg[node][mid] < x) 
            {
                ans = mid;
                lo = mid+1;
            }
            else hi = mid-1;
        }
        return ans + 1;
    }
    int midd = (start+end)/2;
    return query1(node*2,start,midd,l,r,x,v,sg) + query1(node*2+1,midd+1,end,l,r,x,v,sg);
}

ll query2(int node,int start,int end,int l,int r,ll x,vector<ll>&v, vector<vector<ll>>&sg)
{
    if(l>end || r<start) return 0;
    if(l<=start && r>=end)
    {
        int lo = 0, hi = sg[node].size()-1,mid, ans = sg[node].size();
        while(lo<=hi)
        {
            mid = (lo+hi)/2;
            if(sg[node][mid] > x)
            {
                ans = mid;
                hi = mid-1;
            }
            else lo = mid+1;
        }
        return sg[node].size()-ans;
    }
    int midd = (start+end)/2;
    return query2(node*2,start,midd,l,r,x,v,sg) + query2(node*2+1,midd+1,end,l,r,x,v,sg);
}

void solve()
{
    ll n,q,l,r,x; cin >> n ;
    vector<ll>v(n);
    for(int i=0;i<n;i++) cin >> v[i];
    vector<vector<ll>> sg(n*4);
    build(1,0,n-1,v,sg);
    /*for(int i=1;i<=23;i++)
    {
        for(auto e:sg[i]) cout << e << ' '; cout<<endl;
    }*/

    cin >> q; 
    while(q--)
    {
        cin >> l >> x >> r;
        --l; --r; --x;
        ll lsmall = (x==0)? 0 : query1(1,0,n-1,l,x,v[x],v,sg);
        ll rsmall = (x==n-1)? 0 : query1(1,0,n-1,x,r,v[x],v,sg);
        ll lbig = (x==0) ? 0 : query2(1,0,n-1,l,x,v[x],v,sg);
        ll rbig = (x==n-1) ? 0 : query2(1,0,n-1,x,r,v[x],v,sg);

        cout << lsmall*rbig + lbig*rsmall << endl;
    }
}

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