問題文

ある企業は、説明会に参加する学生の選抜コンテストを行いました。 説明会を行おうとしている会場の最大収容可能人数が決まっているため、コンテスト担当者はボーダーラインを何点にするかを悩んでいます。

選抜方法を説明します。

• ボーダーラインが $x$ 点のとき、正の点数を取っている学生のうち $x$ 点以上の得点を得た学生を全て選抜する。
• つまり、$0$ 点の学生は会場の最大収容可能人数に関わらず選抜しない。

あなたには、選抜コンテストにおける $N$ 人の学生の点数が与えられます。 また、会場の候補が $Q$ 個あります。そして、会場の最大収容可能人数はそれぞれ $k_1,k_2,…,k_Q$ です。 ある企業は、説明会をこれらの会場の候補のうちいずれかで開催しようとしています。

あなたの仕事は、それぞれの会場候補で説明会を行う場合について、最小のボーダーラインを出力しなければなりません。 具体的には、$i (1≦i≦Q)$ 番目の会場候補で説明会を行うと仮定したとき、上記の方法に基づいて選抜した学生の数が $k_i$ 人以下となるようなボーダーラインのうち $0$ 以上かつ最小のものを出力してください。

入力

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

$N$ $s_1$ $s_2$ : $s_N$ $Q$ $k_1$ $k_2$ : $k_Q$

• $1$ 行目には、学生の数 $N (1≦N≦100,000)$ が与えられる。
• $2$ 行目から $N$ 行には、選抜コンテストにおける各学生の得点情報が与えられる。そのうち $i (1≦i≦N)$ 行目には、$i$ 番目の学生の得点 $s_i (0≦s_i≦1,000,000)$ が与えられる。
• $2+N$ 行目には、会場候補の数 $Q (1≦Q≦100,000)$ が与えられる。
• $3+N$ 行目から $Q$ 行には、各会場候補の最大収容可能人数が与えられる。そのうち $i (1≦i≦Q)$ 行目には、$i$ 番目の会場の最大収容可能人数 $k_i (0≦k_i≦N)$ が与えられる。

出力

$1$ 行目から $Q$ 行には、各会場候補で説明会を行う場合のボーダーラインを出力せよ。そのうち $i (1≦i≦Q)$ 行目には、$i$ 番目の会場で説明会を行う場合のボーダーラインを出力せよ。

入力例1

15
0
0
0
1
1
2
3
4
5
6
6
6
8
9
10
3
0
4
12

出力例1

11
7
0

とんでもないケースですが、$1$ 番目の会場の最大収容可能人数は $0$ なので、誰も通過させたくありません。それを達成するボーダーラインで最小のものは $11$ 点です。

$2$ 番目の会場の最大収容可能人数は $4$ 人なので、選抜する人数がそれ以下になるようなボーダーラインを設定しなければなりません。 もしボーダーラインを $6$ 点に設定した場合、$6$ 人通過してしまい会場の最大収容可能人数をオーバーしてしまいます。$7$ 点に設定した場合は $3$ 人のみ通過し、会場に収容可能でき、これが最小のボーダーラインです。

$3$ 番目の会場の最大収容可能人数は $12$ 人ですが、ボーダーラインは $0$ 点にします。なぜならば、選抜方法より $0$ 点の学生は通過できないので、正の点数を取った $12$ 人のみが通過するからです。

入力例2

9
3
3
3
2
2
2
1
1
1
1
4

出力例2

3

入力例3

4
0
0
0
0
1
0

出力例3

0

全員が $0$ 点のケースもありえます。 この場合は、どんなボーダーラインに設定しても誰も通過しないので、会場の最大収容可能人数に関わらずボーダーラインは $0$ 点にします。