Young gardener didn’t visit his garden for a long time, and now it’s not very pleasant there: n caterpillars have appeared on the ground.
Kirill decided to use this opportunity to have some fun and organized a competition — "caterpillar crawlrace."
At Kirill’s command all caterpillars start crawling from the ground to the top of a tree. But they get tired pretty fast. After crawling t_{i} cm ith caterpillar needs to rest for t_{i} minutes. During that time it slides down a bit. Crawling speed of a caterpillar is 1 cm/minute, sliding speed — also 1 cm/minute.
Kirill is very much interested to find out how high on the tree is the leading caterpillar at different moments in time.
Input
First line contains one integer n — the number of caterpillars (1 ≤ n ≤ 10^{6}).
Second line contains n integers t_{i} — characteristics of caterpillars (1 ≤ t_{i} ≤ 10^{9}).
In the third line there is a number q — number of moments in time, which Kirill finds interesting (1 ≤ q ≤ 10^{6}).
Remaining q lines contain one query from Kirill each.
A query is described by x_{i} — number of minutes since the start of the competition (1 ≤ x_{i} ≤ 10^{6}).
Output
For every query print in a separate line one integer, that describes how high is the highest caterpillar at the given moment of time.
Sample
input  output 

4
1 3 2 1
12
1
2
3
4
5
6
7
8
9
10
11
12
 1
2
3
2
1
2
1
2
3
2
1
0

Problem Author: Nikita Sivukhin (prepared by Alexey Danilyuk, Nikita Sivukhin)
Problem Source: Ural Regional School Programming Contest 2015