Moving Dots#230
You are given dots that are located on -asis, -th of which has a coordinate x_i. You can move dots. Furthermore, you know, that the dots are so small, that if they do intersect, they will merge into one dot. When two dots do merge, dot with smaller index overlap dot with bigger one, so its index will equal to the smallest index among their indexes. In one second, you can do the following:
Choose one dot among all current existing dots. Let its index be .
Move dot with index from position x_j to (x_j-1) or to (x_j+1).
In other words, in one second you can choose a dot and move either left or right by .
You are given queries. For each query, you need to print the least number of dots that can remain on the plain after seconds passed.
The first line of input contains a single integer (1 \le n \le 2 \cdot 10^5) — number of dots.
The second line of input contain integers x_i (-10^6 \le x_i \le 10^6) — coordinates of the dots on the line.
The next line of input contains one integer (1 \le q \le 2 \cdot 10^5) — number of queries.
The following line of input contain integers t_i (0 \le t_i \le 10^{9}).
Print lines — answers for the corresponding queries.
Example 1
Example 2
( points): n \le 3;
( points): 0 \le x_i \le 20;
( points): t_i \le 20;
( points): n,q \le 3000;
( points): q \le 100;
( points): no additional restrictions.