题意： 求长度为偶数子数组中，排序后，中间偏左和中间偏右的数相同的子数组数目
对于长度为奇数的子数组全部满足，只要求长度为偶数的子数组中满足的个数。
转化为求子数组的总数n*(n+1)/2减去不满足条件的长度为偶数的子数组数目。
发现，如果子数组中小于等于x的数的个数恰好等于子数组长度的一半，那么必然不满足。
而且数组中ai <= 10，可以考虑从1到10枚举每个可能的值，每次枚举，创建一个前缀数组，
如果a[i] <= x, b[i] = 1 否则 b[i] = -1， 这样当一段前缀和为0时，就肯定满足。
如果直接算可能会算重复， 比如一个不符合的子数组，[L,R]中间偏左的数为x,中间偏右的数
为y(x < y), 那么这段区间会算重复y - x 次， （因为枚举x到y之间的数，这段区间和也为0）
那么改变策略，假设当前枚举的值为x,那么碰到a[i] == x时再枚举这个区间。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
void solve() {
int n;
cin >> n;
vector<int> a(n+1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
ll ans = n*(n+1)/2;
for (int x = 1; x <= 10; x++) {
vector<ll> b(n+1);
for (int i = 1; i <= n; i++) {
b[i] = (a[i] <= x ? 1 : -1);
}
for (int i = 2; i <= n; i++) {
b[i] += b[i-1];
}
int pre = 0;
map<int,ll> mp;
for (int i = 1; i <= n; i++) {
if (a[i] == x) {
for (int j = pre; j < i; j++) {
mp[b[j]]++;
}
pre = i;
}
ans -= mp[b[i]];
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while(T--) {
solve();
}
return 0;
}