Кожного разу перед сном Костя заводить будильник, щоб не проспати потім весь день. Кожен будильник дзвонить рівно хвилину та характеризується цілим числом a[i]
- номер хвилини після полуночі, коли він спрацьовує. Кожен будильник спрацьовує на початку відповідної хвилини, та дзвенить рівно хвилину.
Костя точно прокинеться, якщо за деякі m підряд хвилин спрацює мінімум k будильників. Зверніть увагу, Костя враховує тільки ті будильники, які почали дзвонити в даному проміжку часу. Будильники, які почали дзвонити раніше, але продовжують дзвеніти протягом даного проміжку Костя не враховує.
Костя настільки втомився, що хоче проспати весь день і не прокидатися. Визначте мінімальну кількість будильників, які потрібно вимкнути Кості, щоб проспати весь наступний день. Вважайте, що спочатку всі будильники включені.
####Вхідні дані:В першому рядку три числа n, m, k ( 1 ≤ k ≤ n ≤ 10^5
, 1 ≤ m ≤ 10^6
). - кількість будильників та параметри (тривалість і кількість будильників) для пробудження Кості. У другому рядку n різних чисел a[1]
, a[2]
,...,a[n]
(1 ≤a[i]
≤ 10^6
), де ai дорівнює хвилині в яку спрацьовує i-ий будильник. Числа задані в довільному порядку. Вважайте, що Костя живе на планеті, де день дорівнює 10^6
хвилин.####Вихідні дані:Визначте мінімальну кількість будильників, які потрібно вимкнути хлопчику, щоб проспати весь наступний день.
У першому прикладі Кості досить вимкнути перший будильник, який дзвенить у хвилину 3.
У другому прикладі Кості не потрібно вимикати жодного будильника, так як ні за які 10 поспіль хвилин не продзвенить 3 будильника.
У третьому прикладі Костя повинен вимкнути будь-які 6 будильників, щоб продовжити сон.