求任意一个区间中的最大值，最小值 - 单调栈

#define ll long long
const ll maxn = 1e5+5;

ll n;
ll a[maxn], sta[maxn];

void solve() {
    ll top = 0;
    ll sum = 0, ans = 0;
    for(ll i = 1; i <= n; i++){ // 下降
        while(top > 0 && a[sta[top]] < a[i]) {
            ll num = a[sta[top]];
            sum -= num*(sta[top]-sta[top-1]);
            top--;
        } 
        sta[++top] = i;
        sum += a[i]*(sta[top]-sta[top-1]);
        ans += sum;
    }
    
    top = 0, sum = 0;
    for(ll i = 1; i <= n; i++){ // 上升
        while(top > 0 && a[sta[top]] > a[i]){
            ll num = a[sta[top]];
            sum -= num*(sta[top]-sta[top-1]);
            top--;
        }
        sta[++top] = i;
        sum += a[i]*(sta[top]-sta[top-1]);
        ans -= sum;
    }
    cout << ans << ‘\n‘;
}

int main() {
    ll t;
    
    cin >> t;
    while(t--){
        scanf("%lld", &n);
        for(ll i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }        
        solve();
    }
    return 0;
}