#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #define int long long
#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
#define pb push_back
#define lcm(a, b) a *b / __gcd(a, b)
#define endl "\n"
#define start()                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
#define lop(i, n) for (int i = 0; i < n; i++)
#define f first
#define sec second
// #define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;

bool myfnc(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.f > b.f;
}
bool myfnc1(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.f > b.f;
}
bool sortbysec(const tuple<int, int, int> &a,
               const tuple<int, int, int> &b)
{
    // if(get<0>(a) == get<0>(b)) return get<1>(a) < get<1>(b);
    return (get<0>(a) < get<0>(b));
}
struct compare_first
{
    bool operator()(const pair<int, char> &p, const int &x) const
    {
        return p.first < x;
    }
    bool operator()(const int &x, const pair<int, char> &p) const
    {
        return x < p.first;
    }
};

inline void in(int &x) { scanf("%d", &x); }
inline void outN(int &x) { printf("%d\n", x); }
inline void outS(int &x) { printf("%lld ", x); }
long long binpow(long long a, long long b, long long m)
{
    a %= m;
    long long res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

bool bit(int n, int k)
{
    if (n & (1LL << k))
        return true;
    return false;
}

struct pair_hash
{
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2> &pair) const
    {
        auto h1 = std::hash<T1>{}(pair.first);
        auto h2 = std::hash<T2>{}(pair.second);

        std::size_t seed = h1;
        seed ^= h2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);

        return seed;
    }
};

const int mx = 2e5 + 2;

int arr[mx];
int n;

ordered_set st[4 * mx];

void build(int si, int ss, int se)
{

    if (ss == se)
    {
        st[si].insert(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)
{

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }

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

    build(1, 1, n);

    int q;
    cin >> q;
    int l, x, r;
    while (q--)
    {
        cin >> l >> x >> r;

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

        //  cout<<l1<<" "<<arr[x]<<" "<<l2<<endl;

        l1 = query1(1, 1, n, l, x - 1, arr[x]);
        l2 = query(1, 1, n, x + 1, r, arr[x]);

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

        cout << ans << endl;

        // cout << l1 * l2 << endl;
    }
}

signed main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    cin >> t;
    //  in(t);
    //  cin.ignore();

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

    return 0;
}