Server Capacity Plan

Interview

Time limit1sMemory limit256 MB

Summary

Given sorted request times, find the smallest server count so no server exceeds k concurrent 1000ms jobs.

Level: Easy3 of 10
Topics: Sliding window, Intervals
Solved: No attempts yet

Problem

You looked into why one of your systems went down recently, and the answer is overload: it could not keep up with the flood of incoming requests. Adding more servers would let the system handle more requests at once, but you kept putting it off. Now you are finally going to add exactly as many servers as you need.

To predict the traffic ahead, you asked your customers how they plan to use the service, and they sent back the exact timestamp of every request they will ever make. From that you built a list of the $n$ upcoming requests, in milliseconds.

A request is handed to one of your servers the moment it arrives, and it cannot wait. Processing takes exactly 1000 milliseconds, so a request that arrives at time $t$ holds a server from $t$ until just before $t + 1000$ , and at time $t + 1000$ it is already done.

Each server works on at most $k$ requests at the same time. Under that limit, find the smallest number of servers that keeps the system from breaking down again.

Input

The first line contains the number of upcoming requests $n$ and the number of requests one server handles at the same time $k$ . ( $1 \le n \le 100000$ , $1 \le k \le 100000$ )

Each of the next $n$ lines contains one timestamp $t_i$ . ( $0 \le t_i \le 100000$ ) A timestamp is given in milliseconds from the moment you contacted your customers, and the timestamps are sorted in chronological order. Several requests may arrive at the same time.

Output

Print on a single line the minimum number of servers needed to process every incoming request without another breakdown.

Examples5

Example 1
Input
```
2 1
0
1000
```
Expected output
```
1
```
Example 2
Input
```
3 2
1000
1010
1999
```
Expected output
```
2
```
Example 3
Input
```
5 2
500
500
500
500
500
```
Expected output
```
3
```
Example 4
Input
```
4 1
0
1000
2000
3000
```
Expected output
```
1
```
Example 5
Input
```
10 3
0
1
2
3
4
5
6
7
8
9
```
Expected output
```
4
```