みんなで行こう

問題文

競技プログラミング部 Antsのメンバーはrafi2ランドに行こうとしています。 rafi2ランドには $1$ から $N$ と番号付けられた $N$ 個のアトラクションが存在し、 アトラクション $i$ に乗るには $w_i$ 分だけ待たなければいけません。

計画を立てようと思ったharry君は、 $Q$ 個の制限時間、 $a_1$ 分, $a_2$ 分, $\ldots$ , $a_Q$ 分それぞれについて、 その時間内に最大で何種類のアトラクションに乗れるか知りたくなりました。制限時間ちょうどにアトラクションに乗れる場合も制限時間内であるとします。

harry君の代わりにこれらを計算するプログラムを作成してください。ただし、アトラクションに乗っている時間やアトラクション間の移動の時間は $0$ 分であるとします。

制約

• $1 \leq N \leq 10^5$
• $1 \leq w_i \leq 10^9 \ (1 \leq i \leq N)$
• $1 \leq Q \leq 10^5$
• $0 \leq a_i \leq 10^9 \ (1 \leq i \leq Q)$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

出力

$Q$ 行出力せよ。 $i$ 行目には制限時間 $a_i$ 分で乗ることができるアトラクションの種類数の最大値を出力せよ。

サンプル

5
1 3 2 5 10
4
5
10
2
6

2
3
1
3

$1$ つ目の制限時間に対しては、例えばアトラクション $2$ 、 $3$ に乗ることで、制限時間内に $2$ 種類のアトラクションに乗ることができます。また、どのような乗り方をしても $3$ 種類以上のアトラクションに乗ることはできないので答えは $2$ となります。

10
1 18 33 8 13 4 34 23 27 20
7
15
25
11
84
61
1000000000
0

3
3
2
6
5
10
0