[NOI Online #2 入门组] 未了
题目描述
由于触犯天神,Sisyphus 将要接受惩罚。
宙斯命 Sisyphus 推一块巨石上长度为 $L$ 的山坡。Sisyphus 匀速向上推的速度为每年 $v$ 的长度(由于是匀速,故经过 $\frac{1}{2}$ 年将能向上推 $\frac{v}{2}$ 的长度)。然而,宙斯并不希望 Sisyphus 太快到达山顶。宙斯可以施展 $n$ 个魔法,若宙斯施展第 $i$ 个魔法 $(1\leq i \leq n)$,则当 Sisyphus 第一次到达位置 $a_i$ 时,他将会同巨石一起滚落下山底,并从头推起。(滚落的时间忽略不计,即可看作第一次到达位置 $a_i$ 后 Sisyphus 立即从山底重新出发)
例如宙斯施用了 $a_i=3$ 和 $a_i=5$ 的两个魔法。Sisyphus 的速度 $v=1$ ,山坡的长度 $L = 6$,则他推石上山过程如下:
- 用 $3$ 年走到位置 $3$。
- 受 $a_i=3$ 的魔法影响,回到了山底出发。
- 再用 $3$ 年走到位置 $3$,然而因为是第二次到达,$a_i=3$ 的魔法不起作用。
- 用 $2$ 年走到位置 $5$。
- 受 $a_i=5$ 的魔法影响,回到了山底出发。
- 用 $6$ 年从山底走到了山顶。花费的总时间为 $14$ 年。
现在,宙斯有 $q$ 个询问。对于第 $i$ 个询问 $t_i$,宙斯想知道,他最少需要施展多少个魔法才能使 Sisyphus 到达山顶所用的年数大于 $t_i$
输入输出格式
输入格式
第一行三个整数 $n,L,v$ 分别表示魔法的种类数,山坡的长度,Sisyphus 的速度。
第二行 $n$ 个整数。第 $i$ 个整数 $a_i$ 表示第 $i$ 个魔法作用的位置。$(1<i<n)$
第三行一个整数 $q$ 表示宙斯的询问个数。
接下来 $q$ 行每行一个整数,第 $i$ 行的整数 $t_i$ 表示宙斯的第 $i$ 个询问。$(1<i<n)$
输出格式
输出 $q$ 行,每行恰好一个整数,第 $i$ 行的整数对应第 $i$ 个询问的答案。$(1 \leq i\leq q)$
如果宙斯无论如何都不能使 Sisyphus 使用的年数大于 $t_i$,请输出 $-1$。
输入输出样例
输入样例 #1
3 6 3
3 5 1
4
1
3
4
5
输出样例 #1
0
1
2
-1
说明
1. 不使用任何魔法,Sisyphus 需要 $2$ 年走上山顶。
2. 使用魔法 $2$ ,Sisyphus 需要 $\frac{11}{3}$ 年走上山顶。(用时 $\frac{5}{3}$ 年走到魔法 $2$ 的位置并滚落下山,再用时 $\frac{6}{3}=2$ 年走到山顶)
3. 使用魔法 $1,2$ ,Sisyphus 需要 $\frac{14}{3}$ 年走上山顶。
4. 宙斯不能使 Sisyphus 用大于 $5$ 年的时间走上山顶。
对于测试点 $1\sim 8:n=1$。
对于测试点 $9\sim 12:n=2$。
对于测试点 $13\sim 17:n,q\le 1000$。
对于所有测试点:$1 \leq n,q \leq 2 \times 10^5$,$1\leq v\leq L\leq 10^{9}$,$1\leq a_i < L$,$1 \leq t_i\leq 10^9$。
数据保证 $a_i$ 两两不同。