#include <bits/stdc++.h> using namespace std; int n, t, a[100005]; long long s[100005]; void solve() { stack<int> st; st.push(0); memset(a, 0 ,sizeof a); memset(s, 0 ,sizeof s); a[0] = 1e9; long long res = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i - 1] + a[i]; while (st.size() && a[i] >= a[st.top()]) st.pop(); st.push(i); } while (st.size()) { int y = st.top(); st.pop(); if (st.size() == 0) break; int x = st.top(); res += 1LL * (y - x - 1) * a[y] - s[y - 1] + s[x]; } cout << res << '\n'; } main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while (t--) cin >> n, solve(); return 0; }