River Locks
Description
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.
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$.
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$.
Input
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
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$.
Samples
5
4 1 5 4 1
6
1
6
2
3
4
5
-1
3
-1
-1
4
3
5
4 4 4 4 4
6
1
3
6
5
2
4
-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$.