#include <bits/stdc++.h>

using i64 = long long;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    Fenwick(int n = 0) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }   
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }    
    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }    
    int kth(T k) {
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

void solve() {
	int n;
	std::cin >> n;

	std::vector<int> a(n);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		a[i]--;
	}

	i64 ans = 0;
	std::cout << ans;

	Fenwick<int> fen(n);
	int mx = a.front();
	fen.add(mx, 1);

	int cnt = 1;
	std::vector<int> p{0};

	for (int i = 1; i < n; i++) {
		if (a[i] <= mx) {
			ans += cnt - fen.sum(a[i] + 1);
			if (a[i] == mx) {
				p.push_back(i);
			}
		} else {
			if (p.size() == 1) {
				ans += 2;
			} else {
				ans += 2 + i - p[1];
			}
			mx = a[i];
			p.clear();
			p.push_back(i);
		}

		if (fen.rangeSum(a[i], a[i] + 1) == 0) {
			fen.add(a[i], 1);
			cnt++;
		}
		std::cout << " " << ans;
	}

	std::cout << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t;
	std::cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}