[Solution] River Locks solution codeforces

River Locks solution codeforces – Recently in Divanovo, a huge river locks system was built. There are now 𝑛n locks, the 𝑖i-th of them has the volume of 𝑣𝑖vi liters, so that it can contain any amount of water between 00 and 𝑣𝑖vi liters. Each lock has a pipe attached to it. When the pipe is open, 11 liter of water enters the lock every second.

Table of Contents

[Solution] River Locks solution codeforces

The locks system is built in a way to immediately transfer all water exceeding the volume of the lock 𝑖i to the lock 𝑖+1i+1. If the lock 𝑖+1i+1 is also full, water will be transferred further. Water exceeding the volume of the last lock pours out to the river.

River Locks solution codeforcesThe picture illustrates 55 locks with two open pipes at locks 11 and 33. Because locks 1133, and 44 are already filled, effectively the water goes to locks 22 and 55.
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 𝑡𝑗tj seconds.

Please help the mayor to solve this tricky problem and answer his queries.

[Solution] River Locks solution codeforces

The first lines contains one integer 𝑛n (1𝑛2000001≤n≤200000) — the number of locks.

The second lines contains 𝑛n integers 𝑣1,𝑣2,,𝑣𝑛v1,v2,…,vn (1𝑣𝑖1091≤vi≤109)) — volumes of the locks.

The third line contains one integer 𝑞q (1𝑞2000001≤q≤200000) — the number of queries.

Each of the next 𝑞q lines contains one integer 𝑡𝑗tj (1𝑡𝑗1091≤tj≤109) — 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 𝑡𝑗tj seconds all of the locks are filled. If it is impossible to fill all of the locks in given time, print 1−1.

[Solution] River Locks solution codeforces

Examples

input

Copy
5
4 1 5 4 1
6
1
6
2
3
4
5

output

Copy
-1
3
-1
-1
4
3

[Solution] River Locks solution codeforces

input

Copy
5
4 4 4 4 4
6
1
3
6
5
2
4

output

Copy
-1
-1
4
4
-1
5

[Solution] River Locks solution codeforces

There are 66 queries in the first example test.

In the queries 1,3,41,3,4 the answer is 1−1. We need to wait 44 seconds to fill the first lock even if we open all the pipes.

In the sixth query we can open pipes in locks 1133, and 44. After 44 seconds the locks 11 and 44 are full. In the following 11 second 11 liter of water is transferred to the locks 22 and 55. The lock 33 is filled by its own pipe.

Similarly, in the second query one can open pipes in locks 1133, and 44.

In the fifth query one can open pipes 1,2,3,41,2,3,4.

For Solution

Click Here

Leave a Comment