Alarm Clock#8707
Every night before bed, Kostya sets alarms to ensure he doesn't oversleep the entire day. Each alarm rings for exactly one minute and is defined by an integer a_i — the minute after midnight when it rings. Each alarm starts ringing at the beginning of its designated minute and lasts for exactly one minute.
Kostya will definitely wake up if at least alarms ring during any consecutive minutes. It's important to note that Kostya only counts the alarms that start ringing within this interval. Alarms that began ringing before this period but continue into it do not count.
Kostya is so exhausted that he wants to sleep through the entire day without waking up. Your task is to determine the minimum number of alarms Kostya needs to turn off to sleep uninterrupted through the next day. Initially, all alarms are set to ring.
The first line contains three integers , , (1 \le k \le n \le 10^5, 1 \le m \le 10^6) — representing the number of alarms and the parameters for waking Kostya up (duration and number of alarms). The second line contains distinct integers a_1, a_2, ..., a_n (1 \le a_i \le 10^6), where a_i is the minute when the -th alarm rings. These numbers are provided in no particular order. Assume that Kostya lives on a planet where a day consists of 10^6 minutes.
Calculate the minimum number of alarms Kostya needs to disable to sleep through the entire next day without interruption.
Example 1
Example 2
Example 3
In the first example, Kostya only needs to turn off the first alarm, which rings at minute .
In the second example, Kostya doesn't need to turn off any alarms, as there are no alarms ringing within any consecutive minutes.
In the third example, Kostya must turn off any alarms to continue sleeping.