Cho mảng ~A~ gồm ~N~ số nguyên và số nguyên ~K~. Hãy tìm giá trị lớn nhất trong mỗi đoạn con liên tiếp có độ dài ~K~ của mảng.

Cụ thể, với mỗi ~i~ từ ~1~ đến ~N - K + 1~, hãy tính: ~\max(A_i, A_{i+1}, \ldots, A_{i+K-1})~

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le K \le N \le 10^6)~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ ~(-10^9 \le A_i \le 10^9)~.

Dữ liệu ra

In ra ~N - K + 1~ số nguyên trên một dòng, cách nhau bởi dấu cách — giá trị lớn nhất của từng cửa sổ.

Ví dụ

Input:

8 3
1 3 -1 -3 5 3 6 7

Output:

3 3 5 5 6 7

Giải thích:

Giới hạn

Gợi ý: Dùng deque<int> lưu chỉ số các phần tử, duy trì bất biến deque là đơn điệu giảm về giá trị. Đây là kỹ thuật Monotonic Deque kinh điển.