# Percentile P77860

Statement

html

For a list of n numbers in increasing order x0, x1, …, xn−1 and a natural number i between 0 and 100, both of them included, we define the ith percentile as the (unique) number xj 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 x0, xn−1, or (xk−1+xk)/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 x0, x1, …, xn−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++