Moving Dots

You are given $n$ dots that are located on $X$-asis, $i$-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:

1. Choose one dot among all current existing dots. Let its index be $j$.

2. Move dot with index $j$ 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 $1$.

You are given $q$ queries. For each query, you need to print the least number of dots that can remain on the plain after $t$ seconds passed.

Input

The first line of input contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — number of dots.

The second line of input contain $n$ 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 $q$ ($1\le q\le 2\cdot 10^5$) — number of queries.

The following line of input contain $q$ integers $t_i$ ($0\le t_i\le 10^9$).

Output

Print $q$ lines — answers for the corresponding queries.

Examples

Scoring

1. ($11$ points): $n\le 3$;

2. ($16$ points): $0\le x_i\le 20$;

3. ($14$ points): $t_i\le 20$;

4. ($17$ points): $n,q\le 3000$;

5. ($18$ points): $q\le 100$;

6. ($24$ points): no additional restrictions.