考虑拆贡献 \(i - 1 \sim i\)，发现当 \([1, i - 1]\) 的最大值大于 \([i, n]\) 的最小值时 \(i - 1 \sim i\) 产生 \(1\) 的贡献。
考虑枚举左端点 \(j\)，设 \(x = \max\limits_{k=j}^{i-1} a_k\)。设 \(i\) 及 \(i\) 以后第一个 \(< x\) 的数位置是 \(p\)，那么右端点 \(\in [p, n]\)，贡献系数为 \(n - p + 1\)。
这个容易用单调栈优化至 \(O(n \log n)\)，当弹栈时计算贡献即可。
code
// Problem: B2. Range Sorting (Hard Version)
// Contest: Codeforces - Codeforces Round 873 (Div. 1)
// URL: https://codeforces.com/contest/1827/problem/B2
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 300100;
const int logn = 22;
ll n, a[maxn], stk[maxn], top, lg[maxn], f[maxn][logn];
inline ll qmin(int l, int r) {
int k = lg[r - l + 1];
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
inline int ask(int i, int x) {
int l = i + 1, r = n, p = n + 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (qmin(i + 1, mid) < x) {
p = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return p;
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
f[i][0] = a[i];
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 2; i <= n; ++i) {
lg[i] = lg[i >> 1] + 1;
}
ll ans = 0;
top = 0;
for (int i = 1; i <= n; ++i) {
while (top && a[stk[top]] < a[i]) {
ans += (stk[top] - stk[top - 1]) * (n - ask(i, a[stk[top]]) + 1);
--top;
}
ans += stk[top] * (n - i + 1);
stk[++top] = i;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}