Trung Vị Cửa Sổ Trượt

Cho mảng $n$ phần tử. Với mỗi cửa sổ trượt kích thước $k$, tìm trung vị (phần tử ở giữa khi sắp xếp). Nếu $k$ chẵn, chọn phần tử nhỏ hơn trong hai phần tử giữa.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$.

Dòng thứ hai chứa $n$ số nguyên.

Dữ liệu ra

In ra $n-k+1$ số nguyên: trung vị của mỗi cửa sổ.

Ràng buộc

• $1\le k\le n\le 2\times {10}^5$
• $1\le x_i\le {10}^9$

Ví dụ