CF1039E.Summer Oenothera Exhibition

While some people enjoy spending their time solving programming contests, Dina prefers taking beautiful pictures. As soon as Byteland Botanical Garden announced Summer Oenothera Exhibition she decided to test her new camera there.

The exhibition consists of $l = 10^{100}$ Oenothera species arranged in a row and consecutively numbered with integers from $0$ to $l - 1$. Camera lens allows to take a photo of $w$ species on it, i.e. Dina can take a photo containing flowers with indices from $x$ to $x + w - 1$ for some integer $x$ between $0$ and $l - w$. We will denote such photo with $[x, x + w - 1]$.

She has taken $n$ photos, the $i$-th of which (in chronological order) is $[x_i, x_i + w - 1]$ in our notation. She decided to build a time-lapse video from these photos once she discovered that Oenothera blossoms open in the evening.

Dina takes each photo and truncates it, leaving its segment containing exactly $k$ flowers, then she composes a video of these photos keeping their original order and voilà, a beautiful artwork has been created!

A scene is a contiguous sequence of photos such that the set of flowers on them is the same. The change between two scenes is called a cut. For example, consider the first photo contains flowers $[1, 5]$, the second photo contains flowers $[3, 7]$ and the third photo contains flowers $[8, 12]$. If $k = 3$, then Dina can truncate the first and the second photo into $[3, 5]$, and the third photo into $[9, 11]$. First two photos form a scene, third photo also forms a scene and the transition between these two scenes which happens between the second and the third photos is a cut. If $k = 4$, then each of the transitions between photos has to be a cut.

Dina wants the number of cuts to be as small as possible. Please help her! Calculate the minimum possible number of cuts for different values of $k$.

虽然有些人喜欢花时间解决编程竞赛题目，但迪娜更喜欢拍摄美丽的照片。当字节兰植物园宣布举办夏季月见草展时，她决定在那里测试自己的新相机。

展览包含 $l = 10^{100}$ 种月见草，它们排成一列，并依次用从 $0$ 到 $l - 1$ 的整数编号。相机镜头一次可拍摄 $w$ 种月见草，即迪娜可拍摄一个包含编号从 $x$ 到 $x + w - 1$ 的花朵的照片，其中 $x$ 是介于 $0$ 和 $l - w$ 之间的整数。我们用 $[x, x + w - 1]$ 表示这样一张照片。

她共拍摄了 $n$ 张照片，按时间顺序编号，第 $i$ 张照片（按时间顺序）在我们的记号下为 $[x_i, x_i + w - 1]$。当她发现月见草在傍晚开花后，便决定用这些照片制作一部延时视频。

迪娜对每张照片进行截取，仅保留其中恰好包含 $k$ 朵花的一段；然后，她按原始顺序将这些截取后的照片组合成视频——于是，一件精美的艺术作品诞生了！

场景（scene） 指的是一段连续的照片序列，使得这些照片所展示的花朵集合完全相同。两个场景之间的转换称为一次剪切（cut）。例如，假设第一张照片包含花朵 $[1, 5]$，第二张照片包含花朵 $[3, 7]$，第三张照片包含花朵 $[8, 12]$。若 $k = 3$，则迪娜可将第一张和第二张照片均截取为 $[3, 5]$，而将第三张照片截取为 $[9, 11]$。此时，前两张照片构成一个场景，第三张照片也构成一个场景，而发生在第二张与第三张照片之间的这两个场景之间的转换即为一次剪切。若 $k = 4$，则任意两张相邻照片之间都必须有一次剪切。

迪娜希望剪切次数尽可能少。请帮帮她！对不同的 $k$ 值，计算可能的最少剪切次数。

The first line contains three positive integer $n$, $w$, $q$ ($1 \leq n, q \leq 100\,000$, $1 \leq w \leq 10^9$) — the number of taken photos, the number of flowers on a single photo and the number of queries.

Next line contains $n$ non-negative integers $x_i$ ($0 \le x_i \le 10^9$) — the indices of the leftmost flowers on each of the photos.

Next line contains $q$ positive integers $k_i$ ($1 \le k_i \le w$) — the values of $k$ for which you have to solve the problem.

It's guaranteed that all $k_i$ are distinct.

第一行包含三个正整数 $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$ 互不相同。

Print $q$ integers — for each width of the truncated photo $k_i$, the minimum number of cuts that is possible.

输出 $q$ 个整数——对于每个截断照片的宽度 $k_i$，输出可能的最少切割次数。