Problem Description

A certain company has conducted a selection contest for students who wish to attend an information session. Due to the maximum capacity of the venue where the session is to be held, the contest organizers are struggling to decide on the cutoff score.

Here is how the selection process works:

• When the cutoff score is $ x $ points, all students who scored $ x $ points or more are selected, provided they have a positive score.
• In other words, students who scored $ 0 $ points are not selected regardless of the venue's maximum capacity.

You are given the scores of $ N $ students who participated in the selection contest. There are $ Q $ candidate venues for the information session, each with a different maximum capacity, denoted as $k_1, k_2, \ldots, k_Q$. The company intends to hold the information session at one of these candidate venues.

Your task is to output the minimum cutoff score for each candidate venue. Specifically, for the $i\ (1 \leq i \leq Q)$th venue, you must output the smallest cutoff score that ensures no more than $ k_i $ students are selected based on the method described above.

Input Format

The input is provided from standard input in the following format:

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

• The first line contains the number of students $N\ (1 \leq N \leq 100,000)$.
• The next $ N $ lines contain the scores of each student in the selection contest. The $i\ (1 \leq i \leq N)$th line contains the score $s_i\ (0 \leq s_i \leq 1,000,000)$ of the $ i $th student.
• The $ 2 + N $th line contains the number of candidate venues $Q\ (1 \leq Q \leq 100,000)$.
• The next $ Q $ lines contain the maximum capacities of each candidate venue. The $i\ (1 \leq i \leq Q)$th line contains the maximum capacity $k_i\ (0 \leq k_i \leq N)$ of the $ i $th venue.

Output Format

Output $ Q $ lines, each containing the cutoff score for the information session at the corresponding candidate venue. The $i\ (1 \leq i \leq Q)$th line should contain the cutoff score for the $ i $th venue.

Sample Input and Output

Sample Input #1

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

Sample Output #1

11
7
0

Sample Input #2

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

Sample Output #2

3

Sample Input #3

4
0
0
0
0
1
0

Sample Output #3

0

Notes/Hints

Sample Explanation 1

This is an extreme case, but the maximum capacity of the first venue is $ 0 $, so no one should be allowed to pass. The smallest cutoff score that achieves this is $ 11 $ points. For the second venue with a maximum capacity of $ 4 $ people, the cutoff score must be set so that no more than $ 4 $ students are selected. If the cutoff score is set to $ 6 $ points, $ 6 $ students will pass, exceeding the venue's capacity. Setting it to $ 7 $ points allows only $ 3 $ students to pass, which is the minimum cutoff score that fits the venue's capacity. For the third venue with a maximum capacity of $ 12 $ people, the cutoff score is $ 0 $ points. This is because, according to the selection method, students who scored $ 0 $ points cannot pass, so only the $ 12 $ students with positive scores will pass.

Sample Explanation 3

It is also possible that all students scored $ 0 $ points. In this case, no matter what cutoff score is set, no one will pass. Therefore, the cutoff score is $ 0 $ points regardless of the venue's maximum capacity.

见题面 Input 部分

见题面 Output 部分