Percentile P77860

For a list of n numbers in increasing order x₀, x₁, …, x_n−1 and a natural number i between 0 and 100, both of them included, we define the ith percentile as the (unique) number x_j such that j/n < i/100 < j+1/n. Such j will not exists when i=0, i=100, or when k/n = i/100 for any k>0; in these cases, the corresponding percentile is x₀, x_n−1, or (x_k−1+x_k)/2.

Input

The input consists of four lines. In the first one the number n ≤ 1000 is given, and in the following one the n integer numbers x₀, x₁, …, x_n−1, in increasing order and separated by spaces. In the third line there is the number q≤ 101 of questions. The fourth line contains q numbers between 0 and 100, both of them included, that correspond to the q percentiles that your program must compute.

Your program must solve 10 inputs as the described ones in a time of 1 second.

Output

For each one of the q questions, your program must print in a line the corresponding percentile.