In light of the well-ordering principle, Justin decides to well-order the integers with the "English ordering".

In the English ordering, a number is smaller than another if its English equivalent is lexicographically smaller* (i.e. dictionary order). Here are a few examples of the English equivalent of numbers:

• 4321 is "four three two one"
• 880 is "eight eight zero"
• -3 is "negative three"
• -271 is "negative two seven one"

Given $n$ integers as an array $a_i$, your task is to answer $q$ independent queries of the form "How many given integers is less than or equal to $x_i$, in English ordering?".

*String $a$ is lexicographically smaller than string $b$ if $a$ is a prefix of $b$ $(a \neq b)$, or at the first position $i$ for which the two strings differ, $a_i$ comes before $b_i$ in the alphabet. Space is considered smaller than all English characters.

Input

The first line contains an integer $n$, the numbers of integers given.
The second line contains $n$ integers, the array $a_i$.
The third line contains an integer $q$, the number of queries.
The fourth line contains $q$ integers, the number $x_i$ in the $i$-th query.

Output

Output $q$ integers, one integer in each line.

Constraints

For all testcases, $1 \le n, q \le 10^5; |a_i|, |x_i| \le 10^5$.
Subtask 1 (30%): $n, q \le 100; |a_i|, |x_i| \le 9$
Subtask 2 (70%): No additional constraints