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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
using ll = long long;


template<typename T, typename U = T>
struct SegmentTree {
  int n;
  vector<T> tree;

  // ----------

  template<typename VAL_T>
  T get_tree_val(VAL_T& val) {
    return {val};
  }

  T merge(T a, T b) {
    T c;
    std::merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
    return c;
  }

  // ----------

  SegmentTree(int n = 0) : n(n) {
    tree.resize(n<<2);
  }

  template<typename VAL_T>
  SegmentTree(vector<VAL_T>& data) : SegmentTree((int)data.size()) {
    __build(0, 0, n-1, data);
  }

  template<typename VAL_T>
  void __build(int ti, int left, int right, vector<VAL_T>& data) {
    if (left == right) {
      tree[ti] = get_tree_val(data[left]);
      return;
    }

    int tl, tr, tm;
    tl = (ti<<1)+1;
    tr = (ti<<1)+2;
    tm = (left+right)>>1;

    __build(tl, left, tm, data);
    __build(tr, tm+1, right, data);
    tree[ti] = merge(tree[tl], tree[tr]);
  }

  int __query_l(int ti, int left, int right, int l, int r, int x) {
    if ((l <= left) && (right <= r)) {
      int cnt = lower_bound(tree[ti].begin(), tree[ti].end(), x) - tree[ti].begin();
      return cnt;
    }

    int tl, tr, tm;
    tl = (ti<<1)+1;
    tr = (ti<<1)+2;
    tm = (left+right)>>1;

    if (l > tm) return __query_l(tr, tm+1, right, l, r, x);
    if (r <= tm) return __query_l(tl, left, tm, l, r, x);
    return (
      __query_l(tl, left, tm, l, r, x) +
      __query_l(tr, tm+1, right, l, r, x)
    );
  }

  int query_l(int l, int r, int x) { return __query_l(0, 0, n-1, l, r, x); }
};

int main() {
  FAST;
  
  int tc = 1, ti;
  cin >> tc;

  for (ti = 1; ti <= tc; ++ti) {
    ll n, q, i, l, r, l0, l1, r0, r1, ans;
    cin >> n;

    vector<ll> a(n);
    for (i = 0; i < n; ++i) cin >> a[i];

    SegmentTree<vector<ll>> seg(a);

    cin >> q; while (q--) {
      cin >> l >> i >> r;
      --l; --i; --r;

      l0 = l1 = r0 = r1 = 0;
      l0 = seg.query_l(l, i, a[i]);
      l1 = i-l+1 - seg.query_l(l, i, a[i]+1);
      r0 = seg.query_l(i, r, a[i]);
      r1 = r-i+1 - seg.query_l(i, r, a[i]+1);

      ans = l0*r1 + r0*l1;
      cout << ans << "\n";
    }
  }

  return 0;
}