梦境

(dream.cpp 1s/512MB)

题目描述

小 X 做了一个梦，梦里她成为了一名木匠。她面前有 $n$ 根木材，第 $i$ 根木材的长度为 $a_i$，她会按长度从大到小依次处理每根木材，当她处理长度为 $x$ 的木材时（$x>1$），会将它锯成两根长度为 $\lfloor\frac{x}{2}\rfloor$ 的木材（这两根木材之后也要被处理），如果 $x$ 为奇数就会额外产生一个长度为 $1$ 的木材。

恰好小 X 的朋友小 S 正在收集长度为 $1$ 的木材，她手里有一个长度为 $m$ 的数组 $k$，她想知道，对每个 $i$，小 X 处理完第几根木材才能产生至少 $k_i$ 个长度为 $1$ 的木材。保证 $k_i\le \sum a_i$。

输入格式

第一行包含一个整数 $n$（$1\le n\le 10^5$），表示初始木材的根数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$（$2\le a_i\le 10^9$），表示每根木材的长度。

第三行包含一个整数 $m$（$1\le m\le 10^5$）。

第四行包含 $m$ 个整数 $k_1,k_2,\dots ,k_m$（$1\le k_i\le\sum a_i$）。

输出格式

共 $m$ 行。第 $i$ 行输出一个整数，表示满足询问 $k_i$ 所需处理的最少木材根数。

输入输出样例 #1

输入 #1

3
5 3 2
3
1 3 4

输出 #1

1
2
2

数据范围

对于 $30\%$ 的数据，$n\le 1000,a_i\le 20$。

另有 $20\%$ 的数据，$a_i=2$。

另有 $10\%$ 的数据，$k_i\le 10$。

对于 $100\%$ 的数据，$n,m\le 10^5$。