시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

Henry profiles a high load database migration script. The script is the list of n transactions. The i-th transaction consists of ai 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: t1, t2, . . . , tq. 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 ≤ n ≤ 200 000).

The second line consists of n integers a1, a2, . . . , an — the number of queries in each transaction (1 ≤ ai; ∑ai ≤ 106).

The third line contains an integer q — the number of queries (1 ≤ q ≤ 100 000). The fourth line contains q integers t1, t2, . . . , tq (1 ≤ ti ≤ ∑ai).

출력

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

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

예제 입력 1

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

예제 출력 1

2
Impossible
4
5
4
3
3
3