Summer Oenothera Exhibition
Contest: Codeforces Round 507 (Div. 1, based on Olympiad of Metropolises)
Difficulty rating: 3400
Tags: data structures

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$$$.

Input format:
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.

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

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Example input:
3 6 5
2 4 0
1 2 3 4 5

Example output:
0
0
1
1
2

Example input:
6 4 3
1 2 3 4 3 2
1 2 3

Example output:
0
1
2

Editorial:
Let's reconsider this task in terms of segments: we need to split sequence of photos-segments into minimum number of contiguous groups such that there exists a subsegment in each group of length $$$k$$$, which contains inside of each segment of the group.
It's easy to see that if we move right edge of each segment to the left by $$$k$$$, it's required to find a single point which is inside of each segments of the group. Let's consider $$$k$$$ as the length of each segment.
Next, it's always good to include in next group maximum number of segments until they have a on-empty intersection. Therefore, we have solution in $$$O(n \cdot q)$$$ — let's iterate through all segments. If we can add current segment to last group, we add it, else — we create a new group with single current segment.
Furthermore, to find next group, we can use segment tree to perform it in $$$O(\log n)$$$. Let's store minimum and maximum values of $$$x_i$$$, then we descend the tree to find first segment such that maximum left edge is on the right of minimum left edge.
For each $$$i$$$ and $$$x \le n^{1/3}$$$ let's calculate minimum length of segments such that group that starts at element $$$i$$$ contains at least next $$$x$$$ segments. Let's sort all requests in increasing order. We will answer requests in exactly this order. Let's maintain $$$p_i$$$ — length of group for current $$$k$$$, starting at element $$$i$$$ (but $$$p_i \le n^{1/3}$$$). There are $$$n^{4/3}$$$ events of changing this value at most.
Let's also maintain values $$$log_i$$$ — minimum number of groups (and last element of last group) required to jump to element $$$x \ge i + n^{1/3}$$$ or to jump to element $$$x$$$ such that $$$p_x \ge n^{1/3}$$$. It's easy to see that when $$$p_i$$$ changes, only area of radius $$$O(n^{1/3})$$$ is changed for $$$long$$$. Therefore $$$long$$$ may be recalculated in $$$O(n^{5/3} \cdot \log n)$$$ in total.
Now we can simulate requests: we jump using $$$long_i$$$ to the right at least on $$$n^{1/3}$$$, therefore there will be $$$O(q \cdot n^{2/3})$$$ jumps in total.
The solution became $$$O(n^{5/3} \cdot \log n + n^{5/3})$$$ for $$$n = q$$$.
Let's speed up the solution to $$$O(n^{5/3})$$$. Let's change the meaning of $$$long_i$$$ — we allow the last group to be not maximal. Therefore we are now allowed not to recalculate where exactly last maximal group ends. During simulation we need to perform request on segment tree to understand where exactly last maximal group ends.
Now let's do the following: after jump $$$long_i$$$ we iterate through next elements and try to add it to last non-maximal group. If we already added more than $$$n^{2/3}$$$, let's perform a request on tree in $$$\log n$$$.
Therefore the solution performs in $$$O(n^{5/3} + n^{4/3} \cdot \log n)$$$.