#P12279. Distributed Rate Limiting

    ID: 14388 Type: Default 1000ms 256MiB

Distributed Rate Limiting

Distributed Rate Limiting

Little Blue has recently developed an OpenAPI for his service. To prevent malicious abuse, he needs to implement a distributed rate limiting component.

Specifically, in each time interval ([k \cdot N, (k+1) \cdot N)) (with (k = 0, 1, 2, \ldots)), the API is allowed at most (M) successful requests. Any request exceeding this limit should be considered a failure.

Given a list of timestamps representing the moments when a client made API requests, determine how many of these requests were successful.

inputFormat

The first line contains three integers (T), (N), and (M), where (T) is the number of timestamps, (N) defines the length of each time interval, and (M) is the maximum allowed successful requests per interval. The second line contains (T) space-separated integers representing the API request timestamps.

outputFormat

Output a single integer representing the number of successful API requests.

sample

5 10 2
1 2 11 12 13
4

</p>