#include <bits/stdc++.h>
using namespace std;
#define SC               scanf
#define PF               printf
#define ull              unsigned long long
#define ld               long double
#define F                first
#define S                second
#define pb               push_back
#define sort_a(a)        sort(a.begin(),a.end());
#define sort_d(a)        sort(a.rbegin(),a.rend());
#define READ(f)          freopen(f, "r", stdin)
#define WRITE(f)         freopen(f, "w", stdout)
#define rev(s)           reverse(s.begin(),s.end())
#define P(ok)            cout << (ok ? "YES\n": "NO\n")
#define __Heart__              ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define ll long long
typedef pair< ll , ll>                   PII;
const int MX = 2 * 2e5 + 5 ;
ll large[MX] , small[MX] , n;
struct node {
   ll in ;
   ll l ;
   ll r ;
   ll X ;

};
bool compare1(node a, node b)
{

	if (a.X == b.X) return a.l > b.l;
	return a.X > b.X;
}
bool compare2(node a, node b)
{
	if (a.X == b.X) return a.l > b.l;
	return a.X < b.X;
}
void update1(ll index, ll value) {

    while(index <= n){
        large[index] += value ;
        index += index & -index ;
    }
}
ll query1(ll index) {
  ll sum = 0;
  while(index > 0){
    sum += large[index];
    index -= index & -index ;
  }
  return sum ;
}

void update2(ll index, ll value) {

    while(index <= n){
        small[index] += value ;
        index += index & -index ;
    }
}
ll query2(ll index) {
  ll sum = 0;
  while(index > 0){
    sum += small[index];
    index -= index & -index ;
  }
  return sum ;
}

void solve()
{
    cin >> n ;  ll a[n + 5] , l , x , r , q;
    for(int i = 1 ; i <= n ; i++) cin >> a[i] ;
    cin >> q ;
    int mx = n + (2 * q) + 1 ;
    node arrL[mx] , arrS[mx] ;
    for(int i = 1 ; i <= n ; i++) {
        arrL[i].X = arrS[i].X = a[i] ;
        arrL[i].in = arrS[i].in =  0 ;
        arrL[i].l = arrS[i].l = 0 ;
        arrL[i].r = arrS[i].r = i ;
    }
    ll pos = n + 1 , ind = 1;
    for(int i = 1 ; i <= q ; i++){
        cin >> l >> x >> r ;
        arrL[pos].in = arrS[pos].in = ind ;
        arrL[pos].l = arrS[pos].l = l ;
        arrL[pos].r = arrS[pos].r = x ;
        arrL[pos].X = arrS[pos].X = a[x] ;
    //..........................................//
        pos++ , ind++;
        arrL[pos].in = arrS[pos].in = ind ;
        arrL[pos].l = arrS[pos].l = x ;
        arrL[pos].r = arrS[pos].r = r;
        arrL[pos].X = arrS[pos].X = a[x] ;
        pos++ , ind++;
    }
    sort(arrL + 1, arrL + mx, compare1);
    sort(arrS + 1, arrS + mx, compare2);
    for(int i = 0 ; i <= n + 1 ; i++) large[i] = small[i] = 0 ;
    ll countL[q + q + 5] , countS[q + q + 5] ;
    for(int i = 1 ; i <= n + q + q ; i++){
        if(arrL[i].in){
           countL[arrL[i].in] =  query1(arrL[i].r) - query1(arrL[i].l - 1)  ;
        }
        else{
            update1(arrL[i].r , 1) ;
        }
    // ------------------------------------------------//
        if(arrS[i].in){
           countS[arrS[i].in] =  query2(arrS[i].r) - query2(arrS[i].l - 1)  ;
        }
        else{
            update2(arrS[i].r , 1) ;
        }
    }
    for(int i = 1 ; i <= q + q ; i += 2){
        ll Ans = countL[i] * countS[i + 1] + countS[i] * countL[i + 1] ;
        cout << Ans << "\n" ;
    }

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