택시

시간 제한1초메모리 제한128 MB

요약

직선 도로 위 창고에서 출발하는 n대의 택시 연료 거리가 주어질 때, 남은 거리를 이동하는 데 필요한 최소 택시 수를 구하고 불가능하면 0을 출력한다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

바이트아사르는 바이트홀에서 바이트핏까지 택시로 이동하려고 합니다. 두 마을 사이의 거리는 $m$ 킬로미터입니다. 바이트홀에서 바이트핏 방향으로 정확히 $d$ 킬로미터 떨어진 지점에는 택시 $n$ 대가 대기하는 차고지가 있으며, 택시에는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있습니다. $i$ 번 택시에는 정확히 $x_i$ 킬로미터를 달릴 수 있는 연료가 들어 있습니다.

바이트아사르는 경로 위 어느 지점에서든 택시를 갈아탈 수 있습니다. 모든 택시는 차고지에서 출발하지만, 차고지로 다시 돌아올 필요는 없습니다. 바이트아사르가 바이트홀에서 바이트핏까지 이동할 수 있는지 판단하고, 가능하다면 그 여정에 필요한 택시의 최소 대수를 구하세요.

입력

첫째 줄에 세 정수 $m$ , $d$ , $n$ 이 공백 하나로 구분되어 주어집니다 ( $1 \le d \le m \le 10^{18}$ , $1 \le n \le 500{,}000$ ). 각각 바이트홀에서 바이트핏까지의 거리, 바이트홀에서 차고지까지의 거리, 차고지에 있는 택시의 수를 의미합니다.

둘째 줄에 $n$ 개의 정수 $x_1, x_2, \dots, x_n$ 이 공백 하나로 구분되어 주어집니다 ( $1 \le x_i \le 10^{18}$ ). $x_i$ 는 $i$ 번 택시가 달릴 수 있는 최대 거리(킬로미터)입니다.

출력

바이트아사르가 바이트홀에서 바이트핏까지 가는 데 필요한 택시의 최소 대수를 정수 하나로 출력하세요. 이동이 불가능하다면 $0$ 을 출력하세요.

예제4

예제 1
입력
```
42 23 6
20 25 14 27 30 7
```
예상 출력
```
4
```
예제 2
입력
```
100 50 3
10 20 30
```
예상 출력
```
0
```
예제 3
입력
```
100 40 1
140
```
예상 출력
```
1
```
예제 4
입력
```
10 10 2
20 5
```
예상 출력
```
1
```