High Load Database
시간 제한2초메모리 제한512 MB
트랜잭션 크기 배열을 순서를 바꾸지 않고 합이 t 이하인 연속 구간으로 나눌 때 최소 묶음 수를 구하며, 여러 t에 대해 답하고 어떤 트랜잭션이 t보다 크면 Impossible을 출력한다.
문제
Henry는 대용량 데이터베이스 마이그레이션 스크립트의 프로파일을 분석한다. 스크립트는 n개의 트랜잭션으로 이루어진 목록이다. i번째 트랜잭션은 ai개의 쿼리로 구성된다. Henry는 스크립트를 가능한 한 적은 수의 배치로 나누려고 한다. 각 배치는 트랜잭션 하나이거나 연속한 트랜잭션들의 나열이며, 배치에 포함된 쿼리 수의 합은 t를 넘지 않아야 한다.
안타깝게도 Henry는 운영 데이터베이스에서 t의 정확한 값을 알지 못하므로, q개의 가능한 t 값 t1, t2, ..., tq 각각에 대해 최소 배치 수를 추정하려고 한다. 각 값에 대한 배치 수를 Henry가 계산하도록 도와주자.
입력
첫째 줄에는 정수 n이 주어진다. n은 마이그레이션 스크립트의 트랜잭션 수이다 (1 ≤ n ≤ 200 000).
둘째 줄에는 n개의 정수 a1, a2, ..., an이 주어진다. ai는 각 트랜잭션의 쿼리 수이다 (1 ≤ ai; ∑ai ≤ 106).
셋째 줄에는 정수 q가 주어진다. q는 질의의 수이다 (1 ≤ q ≤ 100 000). 넷째 줄에는 q개의 정수 t1, t2, ..., tq가 주어진다 (1 ≤ ti ≤ ∑ai).
출력
q개의 줄을 출력한다. i번째 줄에는 각 배치의 쿼리 수가 최대 ti일 때 가능한 최소 배치 수를 출력한다. 어떤 ti에 대해 스크립트를 배치로 나눌 수 없다면 “Impossible”을 대신 출력한다.
트랜잭션의 순서를 바꿀 수 없으며, 연속한 트랜잭션끼리만 하나의 배치로 묶을 수 있다.