Bisortare

#include <bits/stdc++.h>
using namespace std;
struct bit {
	vector<int> b;
	void resize(int n) {
		b.resize(n);
	}
	void clear() {
		b = vector<int>(b.size());
	}
	void update(int p, int val) {
		int n = b.size() - 1;
		for (int i = p; i <= n; i += i & (-i)) {
			b[i] += val;
		}
	}
	int query(int p) {
		int ans = 0;
		for (int i = p; i >= 1; i -= i & (-i)) {
			ans += b[i];
		}
		return ans;
	}
};
int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int c, n, k;
	cin >> c >> n >> k;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	bit tree;
	tree.resize(n + 1);
	vector<int> st(n + 1);
	for (int i = 1; i <= n; ++i) {
		st[i] = tree.query(a[i] - 1);
		tree.update(a[i], 1);
	}
	tree.clear();
	vector<int> dr(n + 1);
	for (int i = n; i >= 1; --i) {
		dr[i] = tree.query(a[i] - 1);
		tree.update(a[i], 1);
	}
	long long ops = 0;
	multiset<int,greater<int>> delta;
	for (int i = 1; i <= n; ++i) {
		ops += dr[i];
		if (a[i] != 1) {
			delta.insert(dr[i] - st[i]);
		}

	}
	vector<long long> ans(n + 1);
	ans[1] = ops;
	for (int i = 2; i <= n; ++i) {
		int mini = *delta.begin();
		delta.erase(delta.begin());
		ops -= mini;
		ans[i] = ops;
	}
	if (c == 1) {
		cout << ans[k];
		return 0;
	}
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << ' ';
	}
}