#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define dbg(a,b,c,d) cerr<<a<<"  "<<b<<"  "<<c<<"  "<<d<<endl;
#define kill(a) {cout<<a<<endl;continue;}
#define KILL(a) {cout<<a<<endl;return 0;}
#define debug cerr<<"Error Found"<<endl;
#define mem(a,b) memset(a,b,sizeof(a))
#define lcm(a, b) (a/__gcd(a,b))*b
#define w(t) cin>>t;while(t--)
#define pi  2 * acos(0.0)
#define endl "\n"
int t, cs = 0;
const int mxn = 2e5 + 3, mod = 1e9 + 7;
vector<int> tre[mxn * 4], rtre[mxn * 4];
int ar[mxn];
void build(int st, int ed, int node)
{
    for(int i = st; i <= ed; i++)tre[node].push_back(ar[i]), rtre[node].push_back(-ar[i]);
    sort(tre[node].begin(), tre[node].end());
    sort(rtre[node].begin(), rtre[node].end());
    if(st == ed)return;
    int mid = st + ed >> 1;
    build(st, mid, node * 2);
    build(mid + 1, ed, node * 2 + 1);
}

int query(int st, int ed, int node, int l, int r, int x)
{
    if(st > r or ed < l)return 0;
    if(st >= l and ed <= r)
    {
        auto it = lower_bound(tre[node].begin(), tre[node].end(), x) - tre[node].begin();
        return it;
    }
    int mid = st + ed >> 1;
    return query(st, mid, node * 2, l, r, x) + query(mid + 1, ed, node * 2 + 1, l, r, x);
}
int rquery(int st, int ed, int node, int l, int r, int x)
{
    if(st > r or ed < l)return 0;
    if(st >= l and ed <= r)
    {
       auto it = lower_bound(rtre[node].begin(), rtre[node].end(), -x) - rtre[node].begin();
       return it;
    }
    int mid = st + ed >> 1;
    return rquery(st, mid, node * 2, l, r, x) + rquery(mid + 1, ed, node * 2 + 1, l, r, x);
}
void refresh(int n)
{
    for(int i = 1; i <= n; i++)tre[i].clear(), rtre[i].clear();
}
int32_t main()
{
   fast
   w(t)
   {
       int n;
       cin >> n;

       refresh(n * 4);
       for(int i = 1; i <= n; i++)cin >> ar[i];
       build(1, n, 1);
       int q;
       cin >> q;
       while(q--)
       {
           int l, x, r;
           cin >> l >> x >> r;
           int a = query(1, n, 1, l, x, ar[x]), b = rquery(1, n, 1, x, r, ar[x]);
           int64_t ans = 1LL * a * b;
           a = rquery(1, n, 1, l, x, ar[x]), b = query(1, n, 1, x, r, ar[x]);
           ans += 1LL * a * b;
           cout << ans << endl;

       }
   }
}