#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds; 
using namespace std;
 
typedef pair<long long,long long> PLL;
typedef long long LL;
 
#define all(v) v.begin(),v.end()
#define faster {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>    

const LL mod = 1e9 + 7;
const int N = 2e5 + 10;
const LL inf = 1e9;

class MergeSortTree{
    int n;
    vector<vector<int>> tree;
    void build(int id, int le, int ri, vector<int> &a){
        if(le == ri){
            tree[id].push_back(a[le]);
            return;
        }
        int mid = (le + ri) >> 1;
        build(2 * id + 1, le, mid, a);
        build(2 * id + 2, mid + 1, ri, a);
        auto &left = tree[2 * id + 1], &right = tree[2 * id + 2];
        int i = 0, j = 0, n = left.size(), m = right.size();
        while(i < n && j < m){
            if(left[i] < right[j]) tree[id].push_back(left[i]), i++;
            else tree[id].push_back(right[j]), j++;
        }
        while(i < n) tree[id].push_back(left[i]), i++;
        while(j < m) tree[id].push_back(right[j]), j++;
    }
    int queryL(int id, int le, int ri, int l, int r, int val){
        if(le > r || ri < l){
            return 0;
        }
        if(le >= l && ri <= r){
            return ri - le + 1 - (upper_bound(tree[id].begin(), tree[id].end(), val) - tree[id].begin());
        }
        int mid = (le + ri) >> 1;
        return queryL(2 * id + 1, le, mid, l, r, val) + queryL(2 * id + 2, mid + 1, ri, l, r, val);
    }

    int queryS(int id, int le, int ri, int l, int r, int val){
        if(le > r || ri < l){
            return 0;
        }
        
        if(le >= l && ri <= r){
            return (upper_bound(tree[id].begin(), tree[id].end(), val) - tree[id].begin());
        }
        
        int mid = (le + ri) >> 1;
        return queryS(2 * id + 1, le, mid, l, r, val) + queryS(2 * id + 2, mid + 1, ri, l, r, val);
    }
public:
    MergeSortTree(vector<int> &a){
        n = a.size();
        tree.resize(n * 4);
        build(0, 0, n - 1, a);
    }
    int queryS(int l, int r, int val) { return queryS(0, 0, n - 1, l, r, val - 1); }
    int queryL(int l, int r, int val) { return queryL(0, 0, n - 1, l, r, val); }
};

void solve(int test){
    int n, q; cin>>n;
    vector<int> a(n);
    ordered_multiset l, r;
    for(auto &i: a){
        cin>>i;
        r.insert(i);
    }
    MergeSortTree tree(a);
    cin>>q;
    while(q--){
        int l, m, r; cin>>l>>m>>r; l--, m--, r--;
        if(m == l || m == r){
            cout<<0<<'\n'; continue;
        }
        LL ans = 0;
        int left1 = tree.queryS(l, m - 1, a[m]), right1 = tree.queryL(m + 1, r, a[m]);
        ans += (1LL * left1 * right1);
        // cout<<a[m]<<'\n';
        left1 = tree.queryL(l, m - 1, a[m]), right1 = tree.queryS(m + 1, r, a[m]);
        ans += (1LL * left1 * right1);
        cout<<ans<<'\n';
    }
}

signed main(){
    faster
    int t = 1; 
    cin>>t;
    for(int i = 1; i <= t; i++){
        solve(i);
    }
    return 0;
}