问题 3700 --未了

3700: 未了★★★

时间限制: 1 Sec  内存限制: 256 MB
提交: 16  解决: 5
[提交][状态][命题人:]

题目描述

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

宙斯命Sisyphus推一块巨石上长度为L的山坡。Sisyphus匀速向上推的速度为每年v的长度(由于是匀速,故经过1/2年将能向上推v/2的长度)。

然而,宙斯并不希望Sisyphus太快到达山顶。宙斯可以施展n个魔法,若宙斯施展第i个魔法(1i≤n,则当Sisyphus第一次到达位置ai时,他
将会同巨石一起滚落下山底,并从头推起。(滚落的时间忽略不计,即可看作第一次到达位置后Sisyphus立即从山底重新出发)
例如宙斯施用了ai=3与ai=5的两个魔法。Sisyphus的速度v=1,山坡的长度L=6,则他推石上山过程如下:
  • 用3年走到位置3。
  • ai=3的魔法影响,回到了山底出发。
  • 再用3年走到位置3,然而因为是第二次到达,ai=3的魔法不起作用
  • 2年走到位置5。
  • ai=5的魔法影响,回到了山底出发。
  • 用6年从山底走到了山顶。花费的总时间为14年。
现在,宙斯有q个询问。对于第i个询问ti宙斯想知道,他最少需要施展多少个魔法才能使Sisyphus到达山顶所用的年数大于ti

输入

第一行三个整数n,L,v分别表示魔法的种类数,山坡的长度,Sisyphus的速度。
第二行n个整数。第i个整数ai表示第个i魔法作用的位置。(1i≤n
第三行一个整数q表示宙斯的询问个数。
接下来q行每行一个整数,第i行的整数ti表示宙斯的第i个询问。
(1iq)

输出

输出q行,每行恰好一个整数,第i行的整数对应第i个询问的答案。(1iq)
如果宙斯无论如何都不能使Sisyphus使用的年数大于ti,请输出-1。

样例输入
Copy
3 6 3
3 5 1
4
1
3
4
5
样例输出
Copy
0
1
2
-1

提示

样例解释

  • 不使用任何魔法,Sisyphus需要2年走上山顶。
  • 使用魔法2,Sisyphus需要11/3年走上山顶。(用时5/3年走到魔法2的位置并滚落下山,再用时6/3=2年走到山顶)
  • 使用魔法1,2,Sisyphus需要14/3年走上山顶。
  • 宙斯不能使Sisyphus用大于5年的时间走上山顶。
数据范围与提示
对于测试点1 ~ 8:n=1。
对于测试点9~12:n=2。
对于测试点13~17:n,q ≤ 1000。
对于所有测试点:1 ≤ n,≤ 2×105,1 ≤ v ≤ L ≤ 109,1 ≤ a< L,1 ≤ t≤ 109
数据保证ai两两不同。

来源

[提交][状态]