/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
N 日間のイベントが開催されました。i 日目 (1 \leq i \leq N) に配布したパンフレットの枚数は A_i 枚です。
Q 個の質問が与えられます。j 番目の質問 (1 \leq j \leq Q) では正の整数 X_j が与えられるので、以下の答えを出力してください。
- 配布したパンフレットの累計枚数が X_j 枚以上にはじめてなった日が何日目かを出力せよ。そのような日が存在しなければ、代わりに -1 を出力せよ。
制約
- 1 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
- 1 \leq Q \leq 3 \times 10^5
- 1 \leq X_j \leq 10^{12} (1 \leq j \leq Q)
- 入力される数値は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \cdots A_N Q X_1 \vdots X_Q
出力
Q 行出力せよ。
j 行目 (1 \leq j \leq Q) には、j 番目の質問の答えを出力せよ。
入力例 1
5 20 50 30 10 40 4 60 15 110 1000000000000
出力例 1
2 1 4 -1
配布したパンフレットの累計枚数は、N=5 日間のあいだに以下のように変遷します。
- 1 日目の時点の累計枚数は 20 枚。
- 2 日目の時点の累計枚数は 20 + 50 = 70 枚。
- 3 日目の時点の累計枚数は 20 + 50 + 30 = 100 枚。
- 4 日目の時点の累計枚数は 20 + 50 + 30 + 10 = 110 枚。
- 5 日目の時点の累計枚数は 20 + 50 + 30 + 10 + 40 = 150 枚。
各質問の答えは以下のようになります。
- 1 番目の質問において、累計枚数がはじめに 60 枚以上になるのは 2 日目なので、2 を出力します。
- 2 番目の質問において、累計枚数がはじめに 15 枚以上になるのは 1 日目なので、1 を出力します。
- 3 番目の質問において、累計枚数がはじめに 110 枚以上になるのは 4 日目なので、4 を出力します。
- 4 番目の質問において、累計枚数が 1000000000000 枚以上になることはないので、-1 を出力します。
Problem Statement
An event was held over N days. On day i (1 \leq i \leq N), A_i flyers were distributed.
You are given Q questions. In the j-th question (1 \leq j \leq Q), given a positive integer X_j, print the answer to the following:
- On what day did the number of total distributed flyers become X_j or greater for the first time? If there is no such day, report -1 instead.
Constraints
- 1 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
- 1 \leq Q \leq 3 \times 10^5
- 1 \leq X_j \leq 10^{12} (1 \leq j \leq Q)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 \cdots A_N Q X_1 \vdots X_Q
Output
Print Q lines.
The j-th line (1 \leq j \leq Q) should contain the answer to the j-th question.
Sample Input 1
5 20 50 30 10 40 4 60 15 110 1000000000000
Sample Output 1
2 1 4 -1
During the N=5 days, the number of total distributed flyers transitions as follows:
- After day 1: 20 flyers;
- After day 2: 20 + 50 = 70 flyers;
- After day 3: 20 + 50 + 30 = 100 flyers;
- After day 4: 20 + 50 + 30 + 10 = 110 flyers;
- After day 5: 20 + 50 + 30 + 10 + 40 = 150 flyers.
Each question can be answered as follows:
- For the 1-st question, the total flyer count becomes 60 or greater for the first time on day 2, so print 2.
- For the 2-nd question, the total flyer count becomes 15 or greater for the first time on day 1, so print 1.
- For the 3-rd question, the total flyer count becomes 110 or greater for the first time on day 4, so print 4.
- For the 4-th question, the total flyer count never becomes 1000000000000 or greater, so print -1.