C - Self-Stopping Shower 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は銭湯のシャワーを使っています。 このシャワーにはボタンがあります。 時刻 t にボタンを押すと時刻 t から時刻 t+K までの K 秒間お湯が出ます。 お湯が出ているときに再びボタンを押した場合も、最後にボタンを押した時刻から K 秒間お湯が出ます。

N 人の青木君がいて、ボタンを 1 回ずつ押してくれます。 i 人目の青木君は時刻 A_i にボタンを押します。

時刻 0 から時刻 T までの間に常にお湯が出ているようにするために高橋君は最小で何回ボタンを押す必要があるかを求めてください。 ただし、ボタンを押したタイミングと最後にボタンを押してからちょうど K 秒経ったタイミングはいずれもお湯が出ているものとします。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq T \leq 10^9
  • 0 \leq A_i \leq 10^9
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K T  
A_1 A_2 \ldots A_N

出力

答えを 1 行で出力せよ。

入力例 1

3 4 20
6 7 12

出力例 1

4

高橋君は時刻 0,2,10,16 にボタンを押すと、時刻 0 から時刻 20 までの間に常にお湯が出ているようにできます。
ボタンを押す回数が 3 回以下のとき、常にお湯が出ているようにはできないため、答えは 4 です。

入力例 2

9 37 480
12 123 132 213 231 312 321 500 1000

出力例 2

11

Score : 300 points

Problem Statement

Takahashi is using a shower at a public bath. This shower has a button. If the button is pressed at time t, hot water comes out for K seconds, from time t to time t+K. Even if the button is pressed again while hot water is coming out, hot water comes out for K seconds from the time the button was last pressed.

There are N Aokis, each of whom presses the button once. The i-th Aoki presses the button at time A_i.

Find the minimum number of times Takahashi needs to press the button so that hot water is always coming out from time 0 to time T. Here, hot water is considered to be coming out both at the moment the button is pressed and at the moment exactly K seconds after the last press.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq T \leq 10^9
  • 0 \leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K T  
A_1 A_2 \ldots A_N

Output

Print the answer in a single line.

Sample Input 1

3 4 20
6 7 12

Sample Output 1

4

If Takahashi presses the button at times 0,2,10,16, hot water is always coming out from time 0 to time 20.
If he presses the button 3 times or fewer, it is impossible to keep hot water always coming out, so the answer is 4.

Sample Input 2

9 37 480
12 123 132 213 231 312 321 500 1000

Sample Output 2

11