For a list of *n* numbers in increasing order *x*_{0}, *x*_{1},
…, *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 *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*_{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*
≤ 1000 is given, and in the following one the *n* integer numbers *x*_{0}, *x*_{1},
…, *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.

Public test cases

**Input**

10 0 1 2 3 4 5 6 7 8 9 8 0 100 13 20 25 40 75 80

**Output**

0 9 1 1.5 2 3.5 7 7.5

**Input**

20 -4 -3 -3 -3 -1 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 0 5 10 15 20 25 30 78

**Output**

-4 -3.5 -3 -3 -2 -0.5 0 3

**Input**

1 13 5 0 25 50 75 100

**Output**

13 13 13 13 13

Information

- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++