You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

由于触犯天神，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$。

3 6 3
3 5 1
4
1
3
4
5

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$ 两两不同。