Mẻ Rang Cà Phê Trung Nguyên

Mô tả

Tại xưởng rang cà phê Trung Nguyên ở Buôn Ma Thuột, các kỹ sư rang điều hành một dây chuyền rang liên tục. Dọc dây chuyền có n khay hạt cà phê xếp thành một hàng dài, mỗi khay chứa một loại hạt được đánh mã số nguyên dương. Lò rang tự động sẽ lấy k khay liên tiếp để tạo thành một mẻ rang, di chuyển từ đầu đến cuối dây chuyền.

Ví dụ nếu có 6 khay với mã [4, 5, 4, 5, 8, 9] và k = 3, thì lò rang sẽ tạo ra 4 mẻ rang liên tiếp:

• Mẻ 1: các khay 1–3 → [4, 5, 4] → có 2 loại hạt phân biệt.
• Mẻ 2: các khay 2–4 → [5, 4, 5] → có 2 loại hạt phân biệt.
• Mẻ 3: các khay 3–5 → [4, 5, 8] → có 3 loại hạt phân biệt.
• Mẻ 4: các khay 4–6 → [5, 8, 9] → có 3 loại hạt phân biệt.

Nhiệm vụ của bạn là: với mỗi mẻ rang, hãy tính số loại hạt cà phê phân biệt trong mẻ đó. Lấy kết quả của mẻ rang cuối cùng làm đầu ra.

Đầu vào

• Dòng 1: hai số nguyên n và k (1 ≤ k ≤ n), cách nhau bởi dấu cách.
• Dòng 2: n số nguyên dương là mã số các loại hạt cà phê, mỗi số cách nhau bởi dấu cách.

Đầu ra

• Một số nguyên duy nhất: số loại hạt phân biệt trong mẻ rang cuối cùng.

Ràng buộc

• 1 ≤ n ≤ 10^5
• 1 ≤ k ≤ n
• 1 ≤ mã số loại hạt ≤ 10^9

Ví dụ

Ví dụ 1

Đầu vào:

6 3 4 5 4 5 8 9

Đầu ra:

3

Giải thích: Mẻ rang cuối cùng (khay 4–6) gồm các mã [5, 8, 9], tất cả đều khác nhau nên có 3 loại hạt phân biệt.

Ví dụ 2

Đầu vào:

5 5 3 3 3 3 3

Đầu ra:

1

Giải thích: Chỉ có một mẻ rang bao gồm toàn bộ 5 khay, tất cả đều là mã 3 nên chỉ có 1 loại hạt phân biệt.