#include<bits/stdc++.h>
using namespace std;
const long long M=3e5+10,MOD=1000000000;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int>a(n+1);
        for(int i=1;i<=n;i++)cin>>a[i];
        int q;
        cin>>q;
        while(q--){
            int l,x,r;
            cin>>l>>x>>r;
            ll ans=0;
            ll xx=0,y=0;
            for(int i=l;i<x;i++)xx+=(a[i]<a[x]);
            for(int i=x+1;i<=r;i++)y+=(a[x]<a[i]);
            ans+=(xx*y);
            xx=0;
            y=0;
            for(int i=l;i<x;i++)xx+=(a[i]>a[x]);
            for(int i=x+1;i<=r;i++)y+=(a[x]>a[i]);
                ans+=(xx*y);
            cout<<ans<<"\n";
        }
    }




    
   
   return 0;
 
}