首先，若裁判$k$在两者中间（即 $i < k < j$），$|i - k| + |j - k| = k - i + j - k = j - i$ ,恰好等于两者之间的距离，满足题目条件，在其他位置都不满足。

进而，答案就等于严格上升三元组和严格下降三元组的总数。

对于每个位置 $k$（做裁判），定义：

• $L_k$：左侧（编号 $<k$）Rating 小于 $a_k$ 的个数。
  • 那么$(k-1)-L_k$：左侧 Rating 大于 $a_k$ 的个数。
• $R_k$：右侧（编号 $>k$）Rating 小于 $a_k$ 的个数。
  • 那么$(n-k)-R_k$：右侧 Rating 大于 $a_k$ 的个数。

以 $k$ 为裁判的可行比赛数为:

$$L_k \times \bigl((n-k)-R_k\bigr) \;+\; \bigl((k-1)-L_k\bigr)\times R_k. $$

对所有 $k=1\ldots n$ 求和即为答案。

可以维护一个出现次数的树状数组来快速维护前缀和，第一次顺序遍历，通过树状数组的前缀和求$k$前面比$a[k]$小的人的数量，将其存到$l[k]$中。第二次逆序遍历，求出$i$后面比$i$小的数量，存到$r[k]$中，带入公式计算累加到答案即可。

时间复杂度：$O(T \times n \times logn)$

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
using namespace std;
using LL = long long;
const int N = 1e5 + 10;

int n, a[N], tr[N];
LL l[N];

int lowbit(int x){
	return x & -x;
}

LL getsum(int x){
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void update(int x, int c){
    for (int i = x; i < N; i += lowbit(i)) tr[i] += c;
}

void solve(){
	cin >> n;
	LL res = 0;
	memset(tr, 0, sizeof tr);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		update(a[i], 1);
		l[i] = getsum(a[i] - 1);
	}
	memset(tr, 0, sizeof tr);
	for(int i = n; i >= 1; i--){
		update(a[i], 1);
		int y = getsum(a[i] - 1);
		res += l[i] * (n - i - y) + y * (i - l[i] - 1);
	}
	cout << res << endl;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}