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++
- User solutions
- C++