#A2076. [NOI Online #2 入门组] 未了

[NOI Online #2 入门组] 未了

题目描述

由于触犯天神,Sisyphus 将要接受惩罚。

宙斯命 Sisyphus 推一块巨石上长度为 LL 的山坡。Sisyphus 匀速向上推的速度为每年 vv 的长度(由于是匀速,故经过 12\frac{1}{2} 年将能向上推 v2\frac{v}{2} 的长度)。然而,宙斯并不希望 Sisyphus 太快到达山顶。宙斯可以施展 nn 个魔法,若宙斯施展第 ii 个魔法 (1in)(1\leq i \leq n),则当 Sisyphus 第一次到达位置 aia_i 时,他将会同巨石一起滚落下山底,并从头推起。(滚落的时间忽略不计,即可看作第一次到达位置 aia_i 后 Sisyphus 立即从山底重新出发)

例如宙斯施用了 ai=3a_i=3ai=5a_i=5 的两个魔法。Sisyphus 的速度 v=1v=1 ,山坡的长度 L=6L = 6,则他推石上山过程如下:

  • 33 年走到位置 33

  • ai=3a_i=3 的魔法影响,回到了山底出发。

  • 再用 33 年走到位置 33,然而因为是第二次到达,ai=3a_i=3 的魔法不起作用。

  • 22 年走到位置 55

  • ai=5a_i=5 的魔法影响,回到了山底出发。

  • 66 年从山底走到了山顶。花费的总时间为 1414 年。

现在,宙斯有 qq 个询问。对于第 ii 个询问 tit_i,宙斯想知道,他最少需要施展多少个魔法才能使 Sisyphus 到达山顶所用的年数大于 tit_i

输入格式

第一行三个整数 n,L,vn,L,v 分别表示魔法的种类数,山坡的长度,Sisyphus 的速度。

第二行 nn 个整数。第 ii 个整数 aia_i 表示第 ii 个魔法作用的位置。

第三行一个整数 qq 表示宙斯的询问个数。

接下来 qq 行每行一个整数,第 ii 行的整数 tit_i 表示宙斯的第 ii 个询问。

输出格式

输出 qq 行,每行恰好一个整数,第 ii 行的整数对应第 ii 个询问的答案。(1iq)(1 \leq i\leq q)

如果宙斯无论如何都不能使 Sisyphus 使用的年数大于 tit_i,请输出 1-1

3 6 3
3 5 1
4
1
3
4
5

0
1
2
-1

提示

  1. 不使用任何魔法,Sisyphus 需要 22 年走上山顶。
  2. 使用魔法 22 ,Sisyphus 需要 113\frac{11}{3} 年走上山顶。(用时 53\frac{5}{3} 年走到魔法 22 的位置并滚落下山,再用时 63=2\frac{6}{3}=2 年走到山顶)
  3. 使用魔法 1,21,2 ,Sisyphus 需要 143\frac{14}{3} 年走上山顶。
  4. 宙斯不能使 Sisyphus 用大于 55 年的时间走上山顶。

对于测试点 18:n=11\sim 8:n=1

对于测试点 912:n=29\sim 12:n=2

对于测试点 1317:n,q100013\sim 17:n,q\le 1000

对于所有测试点:1n,q2×1051 \leq n,q \leq 2 \times 10^51vL1091\leq v\leq L\leq 10^{9}1ai<L1\leq a_i < L1ti1091 \leq t_i\leq 10^9

数据保证 aia_i 两两不同。