# Petrol stations P40710

Statement

thehtml

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 ≤ 105, 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