#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll long long
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;

const int mx = 2e5 + 2;

int arr[mx], compressed_arr[mx];
int n;

unordered_map<int, int> compress_map; // To store the mapping from original to compressed
ordered_set st[4 * mx];

// Coordinate Compression Function
void coordinate_compress()
{
    vector<int> temp(arr + 1, arr + n + 1);
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end()); // Remove duplicates

    for (int i = 0; i < temp.size(); i++)
    {
        compress_map[temp[i]] = i + 1; // Assign compressed values starting from 1
    }

    for (int i = 1; i <= n; i++)
    {
        compressed_arr[i] = compress_map[arr[i]]; // Compress the original array
    }
}

void build(int si, int ss, int se)
{
    if (ss == se)
    {
        st[si].insert(compressed_arr[ss]);
        return;
    }
    int mid = (ss + se) / 2;
    build(si * 2, ss, mid);
    build(si * 2 + 1, mid + 1, se);
    st[si] = st[si * 2];
    for (auto x : st[si * 2 + 1])
        st[si].insert(x);
}

int query(int si, int ss, int se, int l, int r, int x)
{
    if (se < l || ss > r)
        return 0;
    if (ss >= l && se <= r)
    {
        int kk = st[si].order_of_key(x);
        return kk;
    }
    int mid = (ss + se) / 2;
    return query(si * 2, ss, mid, l, r, x) + query(si * 2 + 1, mid + 1, se, l, r, x);
}

int query1(int si, int ss, int se, int l, int r, int x)
{
    if (se < l || ss > r)
        return 0;
    if (ss >= l && se <= r)
    {
        int kk = st[si].order_of_key(x + 1);
        int sz = st[si].size();
        return sz - kk;
    }
    int mid = (ss + se) / 2;
    return query1(si * 2, ss, mid, l, r, x) + query1(si * 2 + 1, mid + 1, se, l, r, x);
}

void solve(int tc)
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
    }

    coordinate_compress(); // Compress the array before building the segment tree

    for (int i = 1; i <= 4 * n; i++)
    {
        st[i].clear();
    }

    build(1, 1, n);

    int q;
    scanf("%d", &q);
    int l, x, r;
    while (q--)
    {
        scanf("%d %d %d", &l, &x, &r);

        int l1 = query(1, 1, n, l, x - 1, compressed_arr[x]);
        int l2 = query1(1, 1, n, x + 1, r, compressed_arr[x]);
        long long ans = l1 * l2;

        l1 = x - l - l1;
        l2 = r - x - l2;

        long long tp = l1 * l2;
        ans += tp;

        printf("%lld\n", ans);
    }
}

int main()
{
    int t;
    scanf("%d", &t);

    for (int i = 1; i <= t; i++)
    {
        solve(i);
    }

    return 0;
}