Giá trị lớn nhất trên cửa sổ trượt (Sliding Window Maximum)

Nguồn: LeetCode

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $n$ số nguyên và số nguyên $k$. Cửa sổ độ dài $k$ lần lượt dịch từ trái sang phải. Hãy in giá trị lớn nhất của mỗi cửa sổ.

Input

Dòng đầu chứa $n,k$. Dòng thứ hai chứa $n$ số nguyên $a_i$.

Output

In $n-k+1$ số nguyên: giá trị lớn nhất của từng cửa sổ.

Subtask

• Subtask 1 (20%): $1 \le n \le 2000$.
• Subtask 2 (30%): $1 \le n \le 2\cdot 10^4$.
• Subtask 3 (50%): $1 \le n \le 10^5$.

Toàn bộ dữ liệu tuân theo: $1 \le n \le 10^5$, $-10^4 \le a_i \le 10^4$, $1 \le k \le n$.

Ví dụ

Input

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

Output

3 3 5 5 6 7

Giải thích

Mỗi cửa sổ dài $3$ cho một cực đại; theo thứ tự ta nhận được $3,3,5,5,6,7$.