#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, A[200005], q;
struct node{
	int s,e,m,val;
	vector<int>v;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		if(s != e){
			l = new node(s, m);
			r=  new node(m+1, e);
			int in = 0, in2 = 0;
			while(in < l->v.size() || in2 < r->v.size()){
				if(in == l->v.size())v.push_back(r->v[in2]), in2++;
				else if(in2 == r->v.size())v.push_back(l->v[in]), in++;
				else if(l->v[in] < r->v[in2])v.push_back(l->v[in]), in++;
				else v.push_back(r->v[in2]), in2++;
			}
		}
		else v.push_back(A[s]);
	}
	int query(int a, int b, int c){
		if(a > b)return 0;
		if(s == a && b == e)return lower_bound(v.begin(), v.end(), c) - v.begin();
		else{
			int x;
			if(b <= m)x= l->query(a,b,c);
			else if(a > m)x = r->query(a,b,c);
			else x = l->query(a,m,c) + r->query(m+1,b,c);
			
			return x;
		}
	}
	int q2(int a, int b, int c){
		if(a > b)return 0;
		if(s == a && b == e)return upper_bound(v.begin(), v.end(), c) - v.begin();
		else{
			int x;
			if(b <= m)x= l->q2(a,b,c);
			else if(a > m)x = r->q2(a,b,c);
			else x = l->q2(a,m,c) + r->q2(m+1,b,c);
			
			return x;
		}
	}
}*root;
void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++)cin >> A[i];
	root = new node(1, n);
	cin >> q;
	for(int i = 1; i <= q; i++){
		int l, x, r; cin >> l >> x >> r;
		int leftsmol = root->query(l, x - 1, A[x]);
		int leftbig = (x - l) - root->q2(l, x - 1, A[x]);
		int rgtsmol = root->query(x + 1, r, A[x]);
		int rgtbig = (r - x) - root->q2(x + 1, r, A[x]);
		cout << leftsmol * rgtbig + rgtsmol * leftbig << '\n';
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}