Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là tính trung vị của mỗi cửa sổ \(k\) phần tử, từ trái sang phải. Trung vị là phần tử ở giữa khi các phần tử được sắp xếp. Nếu số lượng phần tử là chẵn, có hai trung vị có thể và chúng ta giả định rằng trung vị là số nhỏ hơn trong số chúng.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\): số lượng phần tử và kích thước của cửa sổ \((1 \le k \le n \le 2 \cdot 10^5)\).

Tiếp theo là n số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng \((1 \le x_i \le 10^9)\).

OUTPUT FORMAT

In ra \(n-k+1\) giá trị: các trung vị

Ví dụ:

Input

8 3
2 4 3 5 8 1 2 1

Output

3 4 5 5 2 1

Giải thích ví dụ mẫu

| Vị trí cửa sổ | Cửa sổ            | Trung vị |
|---------------|--------------------|----------|
| 1             | [2, 4, 3]          | 3        |
| 2             | [4, 3, 5]          | 4        |
| 3             | [3, 5, 8]          | 5        |
| 4             | [5, 8, 1]          | 5        |
| 5             | [8, 1, 2]          | 2        |
| 6             | [1, 2, 1]          | 1        |

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House