B. Time to reap the harvest
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In addition to working as a system administrator, Dementy is very keen on growing valerian and adding it into his tea.

Dementy has a map of his one-dimensional field of valerian on his desk. Today he plans to collect his harvest. Dementy mows valerian stalks with a special mower, the blades of which hang above the ground at a certain height that can be adjusted (regulated). Dementy asks the question $$$K$$$ times — how much valerian he will collect if he hangs the blades $$$L$$$ centimeters above the ground?

Formally, the amount of valerian collected by Dementy is determined by the formula:

$$$$$$\sum\limits_{i=1}^N max(a_i - L, 0),$$$$$$

where $$$L$$$ is the height of the blades, $$$a_i$$$ is the height of the $$$i$$$-th bush of valerian.

Input

The first line of the input contains the number $$$N$$$ — the number of valerian bushes in Dementy's garden $$$(1 \le N \le 10^5)$$$.

The second line of the input contains $$$N$$$ number of $$$a_i$$$ — the height of the $$$i$$$-th valerian bush in centimeters $$$(0 \le a_i \le 10^9)$$$.

The third line of the input contains the number $$$K$$$ — the number of requests $$$(1 \le K \le 10^5)$$$.

All the next $$$K$$$ lines contain one number $$$L_i$$$ $$$(0 \le L_i \le 10^9)$$$ — the height to which Dementy wants to raise the blades of the lawn mower.

Output

Type on each of the $$$K$$$ separate lines one number — the answers to the gardener's queries.

Examples
Input
4
0 0 0 0
3
0
1
2
Output
0
0
0
Input
5
4 0 2 1 2
7
0
1
2
3
4
5
6
Output
9
5
2
1
0
0
0