You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Recently in Divanovo, a huge river locks system was built. There are now $$$n$$$ locks, the $$$i$$$-th of them has the volume of $$$v_i$$$ liters, so that it can contain any amount of water between $$$0$$$ and $$$v_i$$$ liters. Each lock has a pipe attached to it. When the pipe is open, $$$1$$$ liter of water enters the lock every second.

The locks system is built in a way to immediately transfer all water exceeding the volume of the lock $$$i$$$ to the lock $$$i + 1$$$. If the lock $$$i + 1$$$ is also full, water will be transferred further. Water exceeding the volume of the last lock pours out to the river.

The picture illustrates $$$5$$$ locks with two open pipes at locks $$$1$$$ and $$$3$$$. Because locks $$$1$$$, $$$3$$$, and $$$4$$$ are already filled, effectively the water goes to locks $$$2$$$ and $$$5$$$.

Note that the volume of the $$$i$$$-th lock may be greater than the volume of the $$$i + 1$$$-th lock.

To make all locks work, you need to completely fill each one of them. The mayor of Divanovo is interested in $$$q$$$ independent queries. For each query, suppose that initially all locks are empty and all pipes are closed. Then, some pipes are opened simultaneously. For the $$$j$$$-th query the mayor asks you to calculate the minimum number of pipes to open so that all locks are filled no later than after $$$t_j$$$ seconds.

Please help the mayor to solve this tricky problem and answer his queries.

## Input Format
The first lines contains one integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the number of locks.

The second lines contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$1 \le v_i \le 10^9$$$)) — volumes of the locks.

The third line contains one integer $$$q$$$ ($$$1 \le q \le 200\,000$$$) — the number of queries.

Each of the next $$$q$$$ lines contains one integer $$$t_j$$$ ($$$1 \le t_j \le 10^9$$$) — the number of seconds you have to fill all the locks in the query $$$j$$$.

## Output Format
Print $$$q$$$ integers. The $$$j$$$-th of them should be equal to the minimum number of pipes to turn on so that after $$$t_j$$$ seconds all of the locks are filled. If it is impossible to fill all of the locks in given time, print $$$-1$$$.

## Examples
```input
5
4 1 5 4 1
6
1
6
2
3
4
5
```
```output
-1
3
-1
-1
4
3
```
-----
```input
5
4 4 4 4 4
6
1
3
6
5
2
4
```
```output
-1
-1
4
4
-1
5
```

## Note
There are $$$6$$$ queries in the first example test.

In the queries $$$1, 3, 4$$$ the answer is $$$-1$$$. We need to wait $$$4$$$ seconds to fill the first lock even if we open all the pipes.

In the sixth query we can open pipes in locks $$$1$$$, $$$3$$$, and $$$4$$$. After $$$4$$$ seconds the locks $$$1$$$ and $$$4$$$ are full. In the following $$$1$$$ second $$$1$$$ liter of water is transferred to the locks $$$2$$$ and $$$5$$$. The lock $$$3$$$ is filled by its own pipe.

Similarly, in the second query one can open pipes in locks $$$1$$$, $$$3$$$, and $$$4$$$.

In the fifth query one can open pipes $$$1, 2, 3, 4$$$.

Now solve the problem and return the code.