River Locks
Contest: Codeforces Round 802 (Div. 2)
Difficulty rating: 1900
Tags: binary search, dp, greedy, math

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
5
4 1 5 4 1
6
1
6
2
3
4
5

Example output:
-1
3
-1
-1
4
3

Example input:
5
4 4 4 4 4
6
1
3
6
5
2
4

Example output:
-1
-1
4
4
-1
5

Editorial:
To begin with, we note that it makes sense to open only some pipe prefix, because we need to fill all the locks, and more left pipes affect the total volume of the baths, which is obviously beneficial. Let's enumerate how many pipes we will open, namely which prefix of pipes we will open and calculate $$$dp_i$$$ - how long it will take to fill the first $$$i$$$ locks if the first $$$i$$$ pipes are open. Let's introduce an auxiliary array $$$pref_i$$$ - the sum of the capacities of the gateways on the prefix $$$i$$$. Then $$$dp_i = max(dp_{i - 1},\ \lceil pref_i / i \rceil)$$$. Let's see why this is so. We need all gateways on prefix $$$i - 1$$$ to be filled, and also that the $$$i$$$-th gateway be filled. Note that if the $$$i$$$-th gateway does not have time to fill up in the time $$$dp_{i - 1}$$$, then it will fill up in the time $$$\lceil pref_i / i \rceil$$$ (filling will occur at the time $$$pref_i / i$$$, but since in the condition we are asked about integer times, we can round up and not use real arithmetic), it turns out when the required amount of water is poured into all the locks in total from all pipes. Now knowing $$$dp_i$$$ for all $$$i$$$ open we can similarly calculate when all n gateways are full. For $$$i$$$ this will be $$$max(dp_i,\ \lceil pref_n / i \rceil)$$$. It is also obvious that when an additional pipe is opened, the time will not increase, therefore we can do a bin search by time and find out the answer for the desired request. If the request $$$t$$$ is less than the minimum filling time for the locks (when all pipes are open), then you need to print $$$-1$$$. Total running time O($$$n + q log(n)$$$).