Bài toán: Tìm trung vị của mỗi cửa sổ ~ k ~ phần tử

Đề bài

Cho một mảng gồm ~ n ~ số nguyên. Nhiệm vụ của bạn là tính trung vị (median) của mỗi cửa sổ ~ k ~ phần tử, từ trái qua phải.

• Trung vị (median) là phần tử nằm giữa khi các phần tử được sắp xếp.
• Nếu ~ k ~ là số chẵn, có hai trung vị có thể xảy ra. Trong trường hợp đó, chọn trung vị nhỏ hơn.

Input

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ k ~: số phần tử trong mảng và kích thước của cửa sổ.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~: các phần tử của mảng.

Output

• In ra ~ n - k + 1 ~ số nguyên: các trung vị của từng cửa sổ.

Ràng buộc

• ~ 1 \leq k \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq x_i \leq 10^9 ~

Ví dụ

Input:

8 3
2 4 3 5 8 1 2 1

Output:

3 4 5 5 2 1

Giải thích:

• Các cửa sổ là:
  • ~ [2, 4, 3] ~: trung vị là 3.
  • ~ [4, 3, 5] ~: trung vị là 4.
  • ~ [3, 5, 8] ~: trung vị là 5.
  • ~ [5, 8, 1] ~: trung vị là 5.
  • ~ [8, 1, 2] ~: trung vị là 2.
  • ~ [1, 2, 1] ~: trung vị là 1.