Problem Description

DEGwer's doctoral dissertation consists of $ N $ pages. Currently, there are $ K $ typos in the dissertation, and the $ i $-th typo ($i = 1, \ldots, K$) is on page $ A_i $.

To submit the dissertation, it is necessary to correct the typos so that no consecutive $ T $ pages contain multiple typos. For the busy DEGwer, please determine the minimum number of typos that should be corrected to meet this requirement.

Input Format

The input is given from the standard input in the following format:

$N\ K\ T$ $A_1\ A_2\ \dots\ A_K$

Output Format

Output the minimum number of typos that should be corrected to submit the dissertation.

Sample Input and Output

Sample Input #1

5 4 3
1 2 4 5

Sample Output #1

2

Sample Input #2

4 8 2
1 1 1 1 1 4 2 2

Sample Output #2

6

Sample Input #3

5 2 3
4 1

Sample Output #3

0

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 2 \times 10^5$
• $1 \leq T \leq N$
• $1 \leq A_i \leq N\ (1 \leq i \leq K)$

Sample Explanation 1

DEGwer's doctoral dissertation consists of 5 pages, with one typo each on pages 1, 2, 4, and 5. For example, if you correct the typos on pages 1 and 4, no consecutive 3 pages will contain multiple typos. It is also confirmed that it is impossible to meet this condition by correcting only one typo. Therefore, output 2 as the minimum number of typos to be corrected.

Sample Explanation 2

Multiple typos can exist on a single page.

Sample Explanation 3

It may not be necessary to correct any typos.

见题面 Input 部分

见题面 Output 部分