https://www.luogu.com.cn/record/87675082

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
ll n, m, k, qaq, cnt, ans = INT_MAX, h[N], pos[N], a[N], t[N];
struct tree {
	ll a[N], c[N];
	int lowbit(int x) {
		return x & -x;
	}
	void add(int x, ll val) {
		a[x] += val;
		for (; x <= cnt; x += lowbit(x)) c[x] += val;
	}
	ll query(int x) {
		ll res = 0;
		for (; x; x -= lowbit(x)) res += c[x];
		return res;
	}
	int Kth(int k) {
		int ans = 0, sum = 0;
		for (int i = 20; i >= 0; i --)
			if (ans + (1 << i) <= cnt && sum + c[ans + (1 << i)] < k)
				ans += 1 << i, sum += c[ans];
		return ans + 1;
	}
} qwq, num;
int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], h[i] = t[i] = a[i];
	sort(t + 1, t + 1 + n), cnt = unique(t + 1, t + 1 + n) - t - 1;
	for (int i = 1; i <= n; i ++)
		a[i] = lower_bound(t + 1, t + 1 + cnt, a[i]) - t;
	for (int i = 1; i < k; i ++)
		qwq.add(a[i], 1), num.add(a[i], h[i]);
	for (int i = 1; i + k - 1 <= n; i ++) {
		int pos = i + k - 1;
		qwq.add(a[pos], 1), num.add(a[pos], h[pos]);
		ll e = (k + 1) / 2, mid = qwq.Kth(e), sum = t[mid];
		ll awa = sum * e - num.query(mid) + num.query(cnt) - num.query(mid) - sum * (k - e);
		if (ans > awa) ans = awa, m = i, qaq = sum;
		qwq.add(a[i], -1), num.add(a[i], -h[i]);
	}
	cout << ans << '\n';
	for (int i = 1; i < m; i ++) cout << h[i] << '\n';
	for (int i = m; i <= m + k - 1; i ++) cout << qaq << '\n';
	for (int i = m + k; i <= n; i ++) cout << h[i] << '\n';
	return 0;
}