Description

CEOI received $M$ tasks over $N$ days. Each task needs $1$ machine working for $1$ day to be completed. CEOI has many machines, and each machine can complete at most one task per day. CEOI requires that each task can be delayed by at most $D$ days. In other words, if a customer submits a task on day $S$, CEOI must finish it by day $S + D$.

Please write a program to find the minimum number of machines needed to complete all tasks on time, under the constraint that each task can be delayed by at most $D$ days.

Input Format

The first line contains three integers: $N$ is the number of days during which CEOI receives tasks, $D$ is the maximum number of days each task can be delayed, and $M$ is the number of tasks.

The second line contains $M$ integers separated by spaces. The $i$-th number represents the day when the $i$-th task is received. There are no tasks after day $N - D$. All tasks are numbered from $1$ to $N$ in order of the input.

Output Format

Output one integer, the minimum number of machines that can complete the tasks.

8 2 12 
1 2 4 2 1 3 5 6 2 3 6 4

2

Hint

For $50\%$ of the testdata, $M \le 10^5$.

For all testdata, $1 \le N \le 10^5$, $0 \le D < N$, $1 \le M < 10^6$.

Translated by ChatGPT 5