Cửa sổ trượt Max bằng hàng đợi hai đầu đơn điệu Monotonic Deque

Mục tiêu kiến thức

• Nắm vững kỹ thuật hàng đợi hai đầu đơn điệu (Monotonic Deque).
• Duy trì tính chất giảm dần để lấy giá trị lớn nhất trong O(1).
• Đạt độ phức tạp thời gian tuyến tính O(N) cho bài toán cửa sổ trượt kích thước K.

Mô tả bài toán

Hệ thống tiền xử lý chuỗi thời gian (time-series stream) cho mô hình Deep Learning tại AI Empire Academy cần trích xuất đặc trưng cực đại địa phương. Cho một mảng gồm N số nguyên A₁, A₂, …, A_N và kích thước cửa sổ trượt K (1 ≤ K ≤ N).

Cửa sổ trượt kích thước K sẽ di chuyển từ đầu mảng tới cuối mảng, mỗi bước dịch sang phải đúng 1 vị trí. Có tất cả N - K + 1 vị trí cửa sổ:

• [1, K], [2, K+1], …, [N - K + 1, N].

Nhiệm vụ của bạn là tìm giá trị lớn nhất trong mỗi cửa sổ trượt và in ra theo đúng thứ tự dịch chuyển. Thuật toán cần đạt độ phức tạp tuyến tính O(N) để xử lý dữ liệu lớn lên tới 10⁶ phần tử.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ K ≤ N ≤ 10⁶.
• -10⁹ ≤ A_i ≤ 10⁹.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.