Trung vị đoạn tịnh tiến

Xem dạng PDF

Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng gồm ~n~ số nguyên. Yêu cầu tính giá trị trung vị cho từng cửa sổ (đoạn con) gồm ~k~ phần tử liên tiếp, xét lần lượt từ trái sang phải.

Giá trị trung vị được xác định là vị trí chính giữa sau khi dãy đã sắp xếp. Nếu kích thước cửa sổ ~k~ là số chẵn, trung vị được quy ước là số nhỏ hơn trong hai phần tử nằm ở giữa.

Input

  • Dòng đầu tiên gồm hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 2 \cdot 10^5~) biểu thị số lượng phần tử và kích thước đoạn con.
  • Dòng tiếp theo chứa ~n~ số nguyên ~x_1, x_2, \dots, x_n~ (~1 \le x_i \le 10^9~) là các phần tử trong mảng.

Output

  • In ra ~n - k + 1~ giá trị trung vị tìm được trên cùng một dòng, phân tách bởi khoảng trắng.

Example

Input:

8 3
2 4 3 5 8 1 2 1

Output:

3 4 5 5 2 1

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.