// PIPRA ||  HABIB
#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;

#define int        long long int
#define pb         push_back
#define all(x)     x.begin(),x.end()
#define allr(x)    x.rbegin(),x.rend()
#define ii         pair<int,int>
#define endl       "\n"

template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) {
    os << '{';
    for (const auto &x : v) os << " " << x;
        return os << '}';
}
using orderedTree = tree<int, null_type, less<int>, 
rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 5;

// seg

int seg[4*N];
int a[N];
vector<vector<int>> tr(4*N);

void build(int i, int low, int high){
    if(low == high){
        seg[i] = a[low];

        tr[i] = {a[low]};
        return;
    }

    int l = (2*i), r = (2*i) + 1;
    int m = (low + high) >> 1;

    build(l, low, m);
    build(r, m+1, high);

    tr[i].resize(tr[l].size() + tr[r].size());
    merge(all(tr[l]), all(tr[r]) , tr[i].begin());
}

int query(int i, int low, int high, int l, int r, int value){
    if(low > r or high < l)     return 0;
    if(low >= l and high <= r){
        int cnt = lower_bound(all(tr[i]) , value) - tr[i].begin();
        return cnt;
    }

    int mid = (low + high) >> 1;
    int li = (2 * i);
    int ri = (2 * i) + 1;

    return  query(li, low, mid, l, r, value) + 
            query(ri, mid+1, high, l, r, value);
}

void pipra(){
    int n;  cin >> n;
    for(int i=1 ; i<=n ; i++)   cin >> a[i];

    build(1, 1, n);

    int q;  cin >> q;
    while(q--){
        int l, m, r;    cin >> l >> m >> r;
        int leftChuto = query(1, 1, n, l, m, a[m]);
        int leftBoro = (m - l + 1) - query(1, 1, n, l, m, a[m]+1);

        int rightchuto = query(1, 1, n, m, r, a[m]);
        int rightBoro = (r - m + 1) - query(1, 1, n, m, r, a[m] + 1);

        int ans = 0;
        ans += leftChuto * rightBoro;
        ans += leftBoro * rightchuto;

        cout << ans << endl;
    }
}

int32_t main(){
    // HABIB
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);

    int t;    cin>>t;
    while(t--) {
        pipra();
    }
    return 0 ;
}