题目描述

Byteasar wants to take a taxi from the town Bytehole to the town Bytepit, which is $m$ kilometres away from Bytehole.

Exactly $d$ kilometres along the way from Bytehole to Bytepit, there is a base of $n$ taxis, numbered from $1$ to $n$.

The taxi no. $i$ has enough fuel to drive exactly $x_i$ kilometres.

Byteasar can change taxis at any point.

All the taxis start at their base but need not return there.

Your task is to determine whether Byteasar can be driven from Bytehole to Bytepit, and if so, what it the minimum number of taxis required for such a journey.

Translation 1:

一条线段有三个点，0为初始位置，d为出租车总部位置，m为家的位置，人要叫车，有n辆车可以提供，每辆车有一个路程上限，并且都从车站出发，叫的车行驶之后不必须回到车站，问最少叫几辆车

.Translation 2:

Byteasar想坐出租车从Bytehole镇到Bytepit镇,恰好有d千米从Bytehole镇到Bytepit镇,这有n个出租车,编号从1到n.第i个出租车有足够的燃料行驶xi千米.Byteasar可以在任意点改变出租车.所有的出租车从他们的总部出发但没必要返回总部.你的任务是判断Byteasar是否能从Bytehole镇到Bytepit镇,如果可以,求出路途需要出租车的最小数量.

输入格式

The first line of the standard input holds three integers, $m$, $d$, and $n$ ($1\le d\le m\le 10^{18}$, $1\le n\le 500\ 000$),separated by single spaces.

Those denote, respectively: the distance from Bytehole to Bytepit,the distance from Bytehole to the taxi base, and the number of taxis at the base.

The second line of input contains $n$ integers, $x_1,x_2,\cdots,x_n$ ($1\le x_i\le 10^{18}$), separated by single spaces.

The number $x_i$ denotes the maximum distance (in kilometres) that the i-th taxi can travel.

第一行的标准输入有三个字母m,d,和n(1≤d≤m≤1e18,1≤n≤500000)中间由空格隔开.

这些分别表示:从Bytehole镇到Bytepit镇的距离,从Bytehole镇到出租车总部的距离,总部的出租车数量.

第二行输入包含n个字母;x1,x2...xn(1≤xi≤1e18),中间由空格隔开.

数字xi表示第i个出租车能行驶的最大距离

输出格式

Your program should print a single integer to the standard output:

the minimum number of taxis Byteasar has to take to get from Bytehole to Bytepit. If getting there is impossible, your program should print the number $0$.

你的程序应该输出一个数字:需要的最小数量的出租车数量.如果不能到达,输出0.

42 23 6
20 25 14 27 30 7

4

提示

提示:此题需开long long