虽然有些人喜欢花时间解决编程竞赛,但 Dina 更喜欢拍摄漂亮的照片。当拜特兰植物园宣布举办夏季月见草展览时,她决定在那里测试她的新相机。
展览由 $$$l = 10^{100}$$$ 月见草属物种组成,排列成一排,并以从 $$$0$$$ 到 $$$l - 1$$$ 的整数连续编号。相机镜头允许拍摄 $$$w$$$ 物种的照片,即 Dina 可以拍摄包含索引从 $$$x$$$ 到 $$$x + w - 1$$$ 的花朵的照片,对于 $$$0$$$ 和 $$$l - w$$$ 之间的某个整数 $$$x$$$。我们将用 $$$[x, x + w - 1]$$$ 表示这样的照片。
她拍摄了 $$$n$$$ 张照片,其中第 $$$i$$$ 张(按时间顺序)在我们的符号中为 $$$[x_i, x_i + w - 1]$$$。当她发现月见草花在晚上开放时,她决定根据这些照片制作一个延时视频。
Dina 拍摄每张照片并将其截断,留下恰好包含 $$$k$$$ 花的片段,然后她将这些照片保持原始顺序制作了一个视频,瞧,一件美丽的艺术品已经创建了!
场景是一系列连续的照片,其中的花朵是相同的。两个场景之间的变化称为剪辑。例如,假设第一张照片包含花朵 $$$[1, 5]$$$,第二张照片包含花朵 $$$[3, 7]$$$,第三张照片包含花朵 $$$[8, 12]$$$。如果 $$$k = 3$$$,则 Dina 可以将第一张和第二张照片截断为 $$$[3, 5]$$$,将第三张照片截断为 $$$[9, 11]$$$。前两张照片形成一个场景,第三张照片也形成一个场景,第二张照片和第三张照片之间发生的这两个场景之间的过渡就是剪切。如果 $$$k = 4$$$,则照片之间的每个过渡都必须是剪切。
Dina 希望切割次数尽可能少。请帮助她!计算不同 $$$k$$$ 值的最小可能切割次数。
输入
第一行包含三个正整数 $$$n$$$, $$$w$$$, $$$q$$$ ($$$1 \leq n, q \leq 100\,000$$$, $$$1 \leq w \leq 10^9$$$) – 拍摄的照片数量,单张照片上的花朵数量和查询数量。
下一行包含 $$$n$$$ 非负整数 $$$x_i$$$ ($$$0 \le x_i \le 10^9$$$) — 每张照片上最左边花朵的索引。
下一行包含 $$$q$$$ 正整数 $$$k_i$$$ ($$$1 \le k_i \le w$$$) — 您必须解决问题的 $$$k$$$ 的值。
保证所有 $$$k_i$$$ 都是不同的。
输出
打印 $$$q$$$ 整数 - 对于截断照片 $$$k_i$$$ 的每个宽度,可能的最小剪切次数。
示例
输入 #1
3 6 5 2 4 0 1 2 3 4 5
输出 #1
0 0 1 1 2
输入 #2
6 4 3 1 2 3 4 3 2 1 2 3
输出 #2
0 1 2