/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
高橋君は N 日間ホテルに滞在します。
ホテルには清掃サービスが存在し、高橋君は N 日間のうちに K 回この清掃サービスを利用しようと考えました。
具体的には滞在を始めてから D_1, D_2, \ldots, D_K 日目に利用しようと考えました。
しかし、実際には清掃サービスはどの連続する L 日間についても M 回までしか利用できないことが判明しました。
より厳密には、1\leq i\leq N-L+1 をみたすすべての整数 i について、
i 日目から (i+L-1) 日目までの間に高々 M 回しかサービスは利用できません。
高橋君は D_1, D_2, \ldots, D_K 日目のうちいくつかの日に利用することを取りやめることによって、この条件をみたすようにしようと思いました。 （1 日も取りやめなくて良い可能性もあります。） 条件をみたすようにするためには、高橋君は K 回のうち最小で何回の利用を取りやめる必要があるか求めてください。
制約
- 1\leq L \leq N \leq 10^{18}
- 1\leq M \leq K \leq 2\times 10^5
- 1\leq D_1<D_2<\cdots<D_K\leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K L M D_1 D_2 \ldots D_K
出力
問題文の条件をみたすために、高橋君は何回清掃サービスの利用を取りやめる必要があるか出力せよ。
入力例 1
10 6 5 2 1 2 3 6 8 10
出力例 1
2
高橋君はどの連続する 5 日間についても清掃サービスを高々 2 回しか利用できません。
2,10 日目の利用を取りやめ、1,3,6,8 日目に利用するようにすることで問題文の条件をみたすようにすることができます。
6 回のうちどの 1 回を取りやめるだけでも問題文の条件をみたすようにできないため、2 を出力します。
入力例 2
10 3 3 1 1 5 10
出力例 2
0
高橋君はどの日もサービスの利用を取りやめる必要はありません。
入力例 3
1000000000000000000 2 1000000000000000000 1 1 1000000000000000000
出力例 3
1
Problem Statement
Takahashi is going to stay at a hotel for N days.
The hotel has a cleaning service, which he is planning to use K times,
on day D_1, day D_2, \ldots, and day D_K, during his N-day visit.
However, it turned out that the service is available at most M times within any consecutive L days.
More formally, for all integers i with 1\leq i\leq N-L+1,
the service is available at most M times from day i through day (i+L-1).
He has decided to cancel some of his plans of using the service on days D_1, D_2, \ldots, and D_K, to meet these conditions. (He may not need to cancel his plan at all.) At least how many days among the K days does he need to cancel his plan of using it to meet the conditions?
Constraints
- 1\leq L \leq N \leq 10^{18}
- 1\leq M \leq K \leq 2\times 10^5
- 1\leq D_1<D_2<\cdots<D_K\leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K L M D_1 D_2 \ldots D_K
Output
Print at least how many times he needs to cancel his plan of using the cleaning service in order to meet the conditions.
Sample Input 1
10 6 5 2 1 2 3 6 8 10
Sample Output 1
2
The cleaning service is available at most twice within any five consecutive days.
The conditions can be met by canceling his plan of using it on day 2 and 10, and using it on day 1,3,6, and 8.
Canceling it only once never satisfies the conditions regardless of which of the six to choose, so print 2.
Sample Input 2
10 3 3 1 1 5 10
Sample Output 2
0
He does not need to cancel his plan at all.
Sample Input 3
1000000000000000000 2 1000000000000000000 1 1 1000000000000000000
Sample Output 3
1