write a go solution for 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.

Input Format:
The first lines contains one integer n (1<=n<=200,000) — the number of locks.

The second lines contains n integers v_1,v_2,...,v_n (1<=v_i<=10^9)) — volumes of the locks.

The third line contains one integer q (1<=q<=200,000) — the number of queries.

Each of the next q lines contains one integer t_j (1<=t_j<=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.

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.. Output only the code with no comments, explanation, or additional text.