/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
DEGwer さんの博士論文は N ページからなります．この博士論文には現在 K 個の誤植が存在し， i 個目の誤植 (i = 1, \ldots, K) は A_i ページにあります．
博士論文を提出するには，どの連続する T ページにも複数の誤植が存在しないように誤植を修正しておく必要があります．コンテストの準備で忙しい DEGwer さんのために，博士論文を提出するために修正すべき最小の誤植の個数を求めてあげてください．
制約
- 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)
入力
入力は以下の形式で標準入力から与えられる．
N \ K \ T A_1 \ A_2 \ \dots \ A_K
出力
博士論文を提出するために修正すべき誤植の個数の最小値を出力せよ．
入力例 1
5 4 3 1 2 4 5
出力例 1
2
DEGwer さんの博士論文は 5 ページからなり， 1 ページ目， 2 ページ目， 4 ページ目， 5 ページ目に 1 個ずつ誤植があります．
例えば 1 ページ目の誤植と 4 ページ目の誤植を修正すると，どの連続する 3 ページにも複数の誤植が存在しない状態になります．一方， 1 個の誤植を修正するだけでこの条件を満たすのは不可能であることも確かめられます．したがって修正すべき最小の誤植の個数として 2 を出力します．
入力例 2
4 8 2 1 1 1 1 1 4 2 2
出力例 2
6
単一のページに複数の誤植が存在することもあります．
入力例 3
5 2 3 4 1
出力例 3
0
誤植を修正する必要がないこともあります．
Score : 100 points
Problem Statement
DEGwer's doctoral dissertation consists of N pages. Currently, there are K typos in this doctoral dissertation, and the i-th typo (i = 1, \ldots, K) is on page A_i.
To submit the doctoral dissertation, it is necessary to correct the typos so that no consecutive T pages contain multiple typos. Please help busy DEGwer, who is preparing this contest, by determining the minimum number of typos that need to be corrected in order to submit the doctoral dissertation.
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)
Input
The input is given from Standard Input in the following format:
N \ K \ T A_1 \ A_2 \ \dots \ A_K
Output
Output the minimum number of typos that need to be corrected to submit the doctoral dissertation.
Sample Input 1
5 4 3 1 2 4 5
Sample Output 1
2
DEGwer's doctoral dissertation consists of 5 pages, with one typo each on the 1st, 2nd, 4th, and 5th pages.
For example, if the typos on the 1st and 4th pages are corrected, then no consecutive 3 pages will have multiple typos. On the other hand, it can also be 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 Input 2
4 8 2 1 1 1 1 1 4 2 2
Sample Output 2
6
There may also be multiple typos on a single page.
Sample Input 3
5 2 3 4 1
Sample Output 3
0
There may be no need to correct any typos.