#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define endl '\n'
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
#define all(v) v.begin(), v.end()
#define pb push_back //
#define mp make_pair
#define fi first                         //
#define se second                        //
#define yes cout << "YES" << endl        //
#define no cout << "NO" << endl          //
#define M 1000000007                     // 1e9+7
#define gcd(a, b) __gcd(a, b)            //
#define lcm(a, b) a *b / gcd(a, b)       //
#define memz(a) memset(a, 0, sizeof(a))  //
#define memn(a) memset(a, -1, sizeof(a)) //
const ll N=2e5+10;
ll n;
ll arr[N];
vector<ll>segtree[4*N];
void build(ll node ,ll start,ll end)
{
    if(start==end)
    {
        segtree[node].resize(0);
        segtree[node].push_back(arr[start]);
        return;
    }
    ll mid=(start+end)/2;
    build(node*2,start,mid);
    build(node*2+1,mid+1,end);
    segtree[node].resize(end-start+1);
    merge(all(segtree[node*2]),all(segtree[node*2+1]),segtree[node].begin());
    return;
}
ll bigquery(ll node,ll start,ll end,ll l,ll r,ll val)
{
    if(start<1||end>n)return 0;
    if(start>r||end<l)return 0;
    if(start>=l&&end<=r)
    {
        return segtree[node].end()- upper_bound(all(segtree[node]),val);
    }
    ll mid=(start+end)/2;
    return bigquery(node*2,start,mid,l,r,val)+bigquery(node*2+1,mid+1,end,l,r,val);
}
ll smallquery(ll node,ll start,ll end,ll l,ll r,ll val)
{
    if(start<1||end>n)return 0;
    if(start>r||end<l)return 0;
    if(start>=l&&end<=r)
    {
        return lower_bound(all(segtree[node]),val)-segtree[node].begin();
    }
    ll mid=(start+end)/2;
    return smallquery(node*2,start,mid,l,r,val)+smallquery(node*2+1,mid+1,end,l,r,val);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll tst;
    cin>>tst;
    for(ll test=1;test<=tst;test++)
    {
        //cout<<"Case "<<test<<": ";
        
        cin>>n;
        for(int i=1;i<=n;i++)cin>>arr[i];
        build(1,1,n);
        ll q;
        cin>>q;
        while(q--)
        {
            ll l,t,r;
            cin>>l>>t>>r;
            cout<<bigquery(1,1,n,l,t-1,arr[t])*smallquery(1,1,n,t+1,r,arr[t])+smallquery(1,1,n,l,t-1,arr[t])*bigquery(1,1,n,t+1,r,arr[t])<<endl;
        }

    }
}