Tom đang đi trên đường thì thấy một cửa hàng bán rất nhiều loại kẹo, vì đang thèm đồ ngọt nên Tom quyết định sẽ vào để mua kẹo ăn. Của hàng kẹo có n viên kẹo đang đặt trên một hàng ngang, loại

kẹo thứ i có độ ngọt là Ai.

Tom không muốn tốn thời gian chọn từng viên kẹo một nên anh quyết định sẽ chọn mua kẹo trong một đoạn liên tiếp. Hiện tại Tom đang có q cách chọn và mỗi cách chọn sẽ là một đoạn từ l đến r. Tuy nhiên, Tom không thích ăn những viên kẹo cùng một độ ngọt nhiều hơn k lần, việc đó sẽ làm cho anh cảm thấy nhạt nhẽo nên Tom muốn nhờ bạn là một lập trình viên tính nhanh cho anh ấy số loại kẹo xuất hiện không quá k lần với mỗi cách chọn kẹo để anh ấy quyết định được cách chọn nào sẽ là hợp lí nhất.

Lưu ý: Những viên kẹo có độ ngọt giống nhau sẽ thuộc cùng một loại kẹo.