Cực tiểu trên cửa sổ trượt

Bối cảnh và bài toán

Một chuỗi đo được quan sát bằng cửa sổ kích thước cố định k. Với mỗi vị trí cửa sổ từ trái sang phải, cần báo giá trị nhỏ nhất trong cửa sổ hiện tại.

Yêu cầu

In minimum của từng cửa sổ độ dài k.

Input

• Dòng 1: n k.
• Dòng 2: n số a[i].

Output

In n-k+1 giá trị minimum.

Ràng buộc

• 1 <= k <= n <= 2 * 10^5
• |a[i]| <= 10^9

Chấm điểm

Ví dụ 1

Input

8 4
2 1 4 5 3 4 1 2

Output

1 1 3 1 1

Giải thích. Minimum của các cửa sổ [2,1,4,5], [1,4,5,3], ... lần lượt như output.

Ví dụ 2

Input

5 1
5 4 3 2 1

Output

5 4 3 2 1

Giải thích. Cửa sổ kích thước 1 có minimum chính là phần tử đó.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set – Sliding Window Minimum.

Tham khảo: https://www.cses.fi/problemset/task/3221