eolymp
bolt
Try our new interface for solving problems
Məsələlər

Будильник

Будильник

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Кожного разу перед сном Костя заводить будильник, щоб не проспати потім весь день. Кожен будильник дзвонить рівно хвилину та характеризується цілим числом 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 хвилин.####Вихідні дані:Визначте мінімальну кількість будильників, які потрібно вимкнути хлопчику, щоб проспати весь наступний день.

Nümunə

Giriş verilənləri #1
3 3 2
3 5 1
Çıxış verilənləri #1
1
Giriş verilənləri #2
5 10 3
12 8 18 25 1
Çıxış verilənləri #2
0
Giriş verilənləri #3
7 7 2
7 3 4 1 6 5 2
Çıxış verilənləri #3
6

Qeyd

У першому прикладі Кості досить вимкнути перший будильник, який дзвенить у хвилину 3.

У другому прикладі Кості не потрібно вимикати жодного будильника, так як ні за які 10 поспіль хвилин не продзвенить 3 будильника.

У третьому прикладі Костя повинен вимкнути будь-які 6 будильників, щоб продовжити сон.

Mənbə ІІІ етап Всеукраїнської олімпіади з інформатики 2019