406447: GYM102411 H High Load Database

Henry profiles a high load database migration script. The script is the list of $$$n$$$ transactions. The $$$i$$$-th transaction consists of $$$a_i$$$ queries. Henry wants to split the script to the minimum possible number of batches, where each batch contains either one transaction or a sequence of consecutive transactions, and the total number of queries in each batch does not exceed $$$t$$$.

Unfortunately, Henry does not know the exact value of $$$t$$$ for the production database, so he is going to estimate the minimum number of batches for $$$q$$$ possible values of $$$t$$$: $$$t_1, t_2, \ldots, t_q$$$. Help Henry to calculate the number of transactions for each of them.

The first line contains a single integer $$$n$$$ — the number of transactions in the migration script ($$$1 \le n \le 200\,000$$$).

The second line consists of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the number of queries in each transaction ($$$1 \le a_i$$$; $$$\sum{a_i} \le 10^6$$$).

The third line contains an integer $$$q$$$ — the number of queries ($$$1 \le q \le 100\,000$$$).

The fourth line contains $$$q$$$ integers $$$t_1, t_2, \ldots, t_q$$$ ($$$1 \le t_i \le \sum{a_i}$$$).

Output $$$q$$$ lines. The $$$i$$$-th line should contain the minimum possible number of batches, having at most $$$t_i$$$ queries each. If it is not possible to split the script into the batches for some $$$t_i$$$, output "Impossible" instead.

Remember that you may not rearrange transactions, only group consecutive transactions in a batch.

6
4 2 3 1 3 4
8
10 2 5 4 6 7 8 8

2
Impossible
4
5
4
3
3
3