Sliding Median

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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define popcnt __builtin_popcount
#define getbit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
// ---------------------------------

void Main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (auto &i : a) {
    cin >> i;
  }
  multiset<int> s;
  for (int i = 0; i < k; i++) {
    s.insert(a[i]);
  }
  auto it = next(s.begin(), (k + 1) / 2 - 1);
  cout << *it << ' ';
  for (int i = k; i < n; i++) {
    if (k == 1) {
      cout << a[i] << ' ';
      continue;
    }
    if (k % 2 == 1) {
      if (a[i - k] > *it || s.find(a[i - k]) == it) {
        it = prev(it);
      }
    }
    if (k % 2 == 0) {
      if (a[i - k] < *it || s.find(a[i - k]) == it) {
        it = next(it);
      }
    }
    s.erase(s.find(a[i - k]));
    s.insert(a[i]);
    if (k % 2 == 1) {
      if (a[i] >= *it) {
        it = next(it);
      }
    }
    if (k % 2 == 0) {
      if (a[i] < *it) {
        it = prev(it);
      }
    }
    cout << *it << ' ';
  }
  cout << '\n';
}

signed main() {
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) Main();
}