진출 기준점

면접 대비

시간 제한5초메모리 제한1024 MB

요약

문제 점수 N개와 기준 점수 Q개가 주어질 때, 각 기준 점수에 도달하는 데 필요한 최소 문제 수를 구합니다.

난이도: 보통10점 중 4점
유형: 정렬, 누적 합, 이분 탐색
정답자: 아직 제출이 없습니다

문제

Bajtazar는 Bajtocka 주니어 정보 올림피아드(BOIJ)에 참가한다. 이 대회의 규칙은 OIJ와 조금 다르다. 1단계에는 정해진 수의 문제가 있고, 문제마다 정해진 점수가 있다(문제마다 점수가 다를 수 있다). 점수는 문제를 완전히 정답으로 처리했을 때만 받으며, 그렇지 않으면 0점이다.

Bajtazar는 게으른 편이라 문제를 풀기보다 몇 문제를 풀어야 2단계에 진출할 수 있을지 생각한다. 대회가 끝나면 BOIJ 운영위원회가 매년 2단계 진출 기준점을 발표한다. 기준점 이상의 점수를 받은 참가자는 모두 진출한다. 문제는 Bajtazar가 대회 중에는 기준점을 알 수 없다는 점이다. 다만 매일 밤 꿈에서 기준점을 알게 되고, 아침이면 그 기준점에 도달하려면 몇 문제를 풀면 충분한지 생각한다. 이 질문에 답하는 프로그램을 짜면 좋겠지만 그는 귀찮아서 당신에게 도움을 청한다.

각 문제의 점수와 가능한 기준점을 입력받아, 기준점마다 2단계에 진출하는 데 필요한 최소 해결 문제 수를 구해 표준 출력으로 내보내는 프로그램을 작성하라.

입력

첫 줄에 자연수 $N$ ( $1 \le N \le 200000$ )이 주어진다. 이는 1단계의 문제 수이다. 둘째 줄에는 자연수 $N$ 개가 공백으로 구분되어 주어지며, $i$ 번째 수 $V_i$ ( $1 \le V_i \le 10^9$ )는 $i$ 번째 문제를 정답으로 처리했을 때 받는 점수이다.

셋째 줄에는 Bajtazar가 꾼 꿈의 수를 나타내는 자연수 $Q$ ( $1 \le Q \le 200000$ )가 주어진다. 이어지는 $Q$ 개의 줄에는 각각 자연수 $P_i$ ( $1 \le P_i \le V_1 + V_2 + \cdots + V_N$ )가 한 개씩 주어진다. 이는 $i$ 번째 꿈에서 본 2단계 진출 기준점이다.

출력

정확히 $Q$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 꿈의 기준점에서 2단계에 진출하기 위해 해결해야 하는 문제 수의 최솟값을 자연수 하나로 출력한다.

예제1

예제 1
입력
```
6
3 2 1 1 5 1
3
3
13
9
```
예상 출력
```
1
6
3
```