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 t_i cm i-th 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.

First line contains one integer n — the number of caterpillars (1 ≤ n ≤ 10⁶).

Second line contains n integers t_i — characteristics of caterpillars (1 ≤ t_i ≤ 10⁹).

In the third line there is a number q — number of moments in time, which Kirill finds interesting (1 ≤ q ≤ 10⁶).

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⁶).

For every query print in a separate line one integer, that describes how high is the highest caterpillar at the given moment of time.