ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2064. Caterpillars

Time limit: 3.0 second
Memory limit: 64 MB
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 crawl-race."
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 ti cm i-th caterpillar needs to rest for ti 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 ≤ 106).
Second line contains n integers ti — characteristics of caterpillars (1 ≤ ti ≤ 109).
In the third line there is a number q — number of moments in time, which Kirill finds interesting (1 ≤ q ≤ 106).
Remaining q lines contain one query from Kirill each. A query is described by xi — number of minutes since the start of the competition (1 ≤ xi ≤ 106).

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

inputoutput
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