River Locks

2000ms

262144K

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.

$\text{[math]}$ 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:

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

Sample Input:

Sample Output:

-1
3
-1
-1
4
3

Sample Input:

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

Informação

Provedor Codeforces

Código CF1700D