题目描述

给定一个长度为 $N$ 的数列 $A$，然后进行若干次询问，每次给定一个整数 $T$， 求出最大的 $k$， 满足 $\sum \limits_{i=1}^k{A[i]} \le T$。你的算法必须是在线的（必须即时回答每一个询问， 不能等待收到所有询问后再统一处理），假设 $0 \le T \le \sum\limits _{i=1}^n{A[i]}$。

格式

输入

第一行一个整数 $n(1 \le n \leq 5 \times10^5)$， 表示数列A的长度。第二行有空格隔开的 $n$ 个数 $A_i(0 \le A_i \le 10^9)$。第三行一个整数 $q(1 \le q \le 5\times10^5)$，表示有 $q$ 次询问。接下来的 $q$ 行，每行一个$T_j$。

输出

$q$行，每一行对应输入的每一个 $T_j$ 的最大的 $k$。

样例

5
1 2 3 4 5
1
6

3

数据规模

20%的数据，$1 \le n, q \le 100$，

另30%的数据，$1 \le n, q \le 1000$，

100%的数据，$1 \le n，q\le 5 \times 10^5$。