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

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