A15236 | River Locks

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$ .