Code : Range Minimum Sum

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

void solve(vector<int> &a) {
    int n = a.size();

    vector<long long> f(n);
    auto add = [&](int l, int r, long long delta) {
        if (l < 0 || r >= n || l > r) {
            return;
        }
        for (int i = l; i <= r; i++) {
            f[i] += delta;
        }
    };

    set<pair<int, int>> store;
    for (int i = 0; i < n; i++) {
        store.insert({a[i], i});
    }

    set<int> alive;
    for (auto ele : store) {
        int i = ele.second;

        auto r_itr = alive.upper_bound(i);
        int R = n;
        if (r_itr != alive.end()) {
            R = *r_itr;
        }

        auto l_itr = alive.upper_bound(i);
        int L = -1;
        if (l_itr != alive.begin()) {
            l_itr--;
            L = *l_itr;
        }

        long long A = i - L;
        long long B = R - i;
        long long x = a[i];
        add(0, L - 1, A * B * x);
        add(R + 1, n - 1, A * B * x);

        add(L + 1, i - 1, (A - 1) * B * x);
        add(i + 1, R - 1, A * (B - 1) * x);

        int RR = n;
        if (R < n) {
            r_itr++;
            if (r_itr != alive.end()) {
                RR = *r_itr;
            }
        }

        int LL = -1;
        if (L >= 0) {
            if (l_itr != alive.begin()) {
                l_itr--;
                LL = *l_itr;
            }
        }

        long long P = i - LL - 1;
        long long Q = RR - i - 1;
        add(L, L, P * B * x);
        add(R, R, A * Q * x);
        alive.insert(i);
    }

    for (int i = 0; i < n; i++) {
        cout << f[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n, x;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
}

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

void solve(vector<int> &a) {
    int n = a.size();

    vector<long long> f(n);
    auto add = [&](int l, int r, long long delta) {
        if (l < 0 || r >= n || l > r) {
            return;
        }
        f[l] += delta;
        if (r + 1 < n) {
            f[r + 1] -= delta;
        }
    };

    set<pair<int, int>> store;
    for (int i = 0; i < n; i++) {
        store.insert({a[i], i});
    }

    set<int> alive;
    for (auto ele : store) {
        int i = ele.second;

        auto r_itr = alive.upper_bound(i);
        int R = n;
        if (r_itr != alive.end()) {
            R = *r_itr;
        }

        auto l_itr = alive.upper_bound(i);
        int L = -1;
        if (l_itr != alive.begin()) {
            l_itr--;
            L = *l_itr;
        }

        long long A = i - L;
        long long B = R - i;
        long long x = a[i];
        add(0, L - 1, A * B * x);
        add(R + 1, n - 1, A * B * x);

        add(L + 1, i - 1, (A - 1) * B * x);
        add(i + 1, R - 1, A * (B - 1) * x);

        int RR = n;
        if (R < n) {
            r_itr++;
            if (r_itr != alive.end()) {
                RR = *r_itr;
            }
        }

        int LL = -1;
        if (L >= 0) {
            if (l_itr != alive.begin()) {
                l_itr--;
                LL = *l_itr;
            }
        }

        long long P = i - LL - 1;
        long long Q = RR - i - 1;
        add(L, L, P * B * x);
        add(R, R, A * Q * x);
        alive.insert(i);
    }

    // Convert the difference array to prefix sum array.
    for (int i = 1; i < n; i++) {
        f[i] += f[i - 1];
    }
    for (int i = 0; i < n; i++) {
        cout << f[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n, x;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
}