A car driver needs to plan a journey following a highway. With the tank full he can drive for at most x kms. Knowing the location of the n petrol stations on the road, which is the minimum number of refill stops necessary to travel for at least D kms? Assume that, initially, the tank of the car is full of gasoline.

Input

Input is all natural numbers, and consists of several cases.
Every case begins with x and D,
followed by n,
followed by the distances in kms
from the departure point to each petrol station.
Assume x > 0, D > 0, n ≤ 10^{5},
and that all the given distances are different and between 1 and D−1.
For all the given cases, it is always possible to reach the km D.

Output

For every case, print the minimum number of stops to travel for at least D kms.

Public test cases

**Input**

2 5 3 1 3 4 3 10 4 1 8 6 4 15 10 6 5 2 9 4 1 3

**Output**

2 4 0

Information

- Author
- Amalia Duch
- Language
- English
- Official solutions
- C++ Python Python
- User solutions
- C++ Python