Percentile P77860

For a list of $n$ numbers in increasing order $x_0, x_1, \ldots, x_{n-1}$ and a natural number $i$ between 0 and 100, both of them included, we define the $i$th percentile as the (unique) number $x_j$ such that $\frac{j}{n} < \frac{i}{100} < \frac{j+1}{n}$. Such $j$ will not exists when $i=0$, $i=100$, or when $\frac{k}{n} = \frac{i}{100}$ for any $k>0$; in these cases, the corresponding percentile is $x_0$, $x_{n-1}$, or $(x_{k-1}+x_{k})/2$.

Input

The input consists of four lines. In the first one the number $n \leq 1000$ is given, and in the following one the $n$ integer numbers $x_0, x_1, \ldots, x_{n-1}$, in increasing order and separated by spaces. In the third line there is the number $q\le 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.