A - Airport Bus Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

高橋空港には，毎日飛行機で N 人の乗客が到着します． i 番目の乗客は時刻 T_i に到着します．

高橋空港に到着する乗客は全員バスで市内へ移動します．どのバスも定員は C 人であり，C 人以下の乗客を乗せることができます． 飛行機の乗客は，飛行機の到着時刻よりも早く出発するバスには乗ることができません． また，飛行機の到着時刻から K の時間が経過した後にもバスに乗れていないと，怒り出してしまいます． そのため，i 番目の乗客は，出発時刻が T_i 以上 T_i + K 以下であるようなバスに乗れるようにしないといけません．

この条件のもとで，うまくバスの出発時刻を定めるとき，必要なバスの数の最小値を求めてください． ただし，バスの出発時刻は必ずしも整数である必要はなく，同じ時刻に出発するバスが複数あってもかまいません．

制約

  • 2 \leq N \leq 100000
  • 1 \leq C \leq 10^9
  • 1 \leq K \leq 10^9
  • 1 \leq T_i \leq 10^9
  • C, K, T_i は整数

入力

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

N C K
T_1
T_2
:
T_N

出力

必要なバスの数の最小値を出力せよ．

入力例 1

5 3 5
1
2
3
6
12

出力例 1

3

例えば，時刻 4.5, 6, 12 にバスを出発させ，次のように乗客をバスに乗せるとよいです．

  • 時刻 4.5 に出発するバスには，時刻 2, 3 に到着する乗客を乗せる．
  • 時刻 6 に出発するバスには，時刻 1, 6 に到着する乗客を乗せる．
  • 時刻 12 に出発するバスには，時刻 12 に到着する乗客を乗せる．

入力例 2

6 3 3
7
6
2
8
10
6

出力例 2

3

Score : 300 points

Problem Statement

Every day, N passengers arrive at Takahashi Airport. The i-th passenger arrives at time T_i.

Every passenger arrived at Takahashi airport travels to the city by bus. Each bus can accommodate up to C passengers. Naturally, a passenger cannot take a bus that departs earlier than the airplane arrives at the airport. Also, a passenger will get angry if he/she is still unable to take a bus K units of time after the arrival of the airplane. For that reason, it is necessary to arrange buses so that the i-th passenger can take a bus departing at time between T_i and T_i + K (inclusive).

When setting the departure times for buses under this condition, find the minimum required number of buses. Here, the departure time for each bus does not need to be an integer, and there may be multiple buses that depart at the same time.

Constraints

  • 2 \leq N \leq 100000
  • 1 \leq C \leq 10^9
  • 1 \leq K \leq 10^9
  • 1 \leq T_i \leq 10^9
  • C, K and T_i are integers.

Input

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

N C K
T_1
T_2
:
T_N

Output

Print the minimum required number of buses.

Sample Input 1

5 3 5
1
2
3
6
12

Sample Output 1

3

For example, the following three buses are enough:

  • A bus departing at time 4.5, that carries the passengers arriving at time 2 and 3.
  • A bus departing at time 6, that carries the passengers arriving at time 1 and 6.
  • A bus departing at time 12, that carries the passenger arriving at time 12.

Sample Input 2

6 3 3
7
6
2
8
10
6

Sample Output 2

3