H. Zaglol vs. the British Occupation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Zaglol has a fight against a row of $$$n$$$ members of the British Occupation; the $$$i$$$-th person has power $$$a_i$$$. Zaglol has a magic sword with power $$$x$$$.

Zaglol can kill a person only if the sword's current power is at least that person's power. However, each time he kills a person with power $$$a_i$$$, the sword's power decreases by $$$a_i$$$.

For each query (a given sword power $$$x$$$) determine the maximum number of members of the British Occupation Zaglol can kill.

Each query is independent (Zaglol starts fresh for every query).

Input

The first line contains a single integer $$$n (1 ≤ n ≤ 10^5)$$$ — the number of people.

The second line contains $$$n$$$ integers $$$a₁, a₂, ..., aₙ$$$ $$$(1 ≤ aᵢ ≤ 10^9)$$$ — the power of each person.

The third line contains a single integer $$$q (1 ≤ q ≤ 10^5)$$$ — the number of queries.

The next $$$q$$$ lines each contain a single integer $$$x (0 ≤ x ≤ 10^9)$$$ — the sword power for that query.

Output

For each query, print a single integer on its own line: the maximum number of members of the British Occupation Zaglol can kill with a sword of power $$$x$$$.

Example
Input
7
5 1 3 7 2 3 10
5
0
2
3
6
10
Output
0
1
2
3
4