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

Sample Test Cases

Input Output
10
0 1 2 3 4 5 6 7 8 9
3
2 6 9
9
7
4

In English ordering, eight < five < four < nine < one < seven < six < three < two < zero.

5
5 -3 8145 0 69
3
-6 2 111
2
4
3

In English ordering, $8145 < 5 < (-6) < -3 < (111) < 69 < (2) < 0$.

Click to copy.

Scoring: Per Subtask
Authored by s17f18
Appeared in 2025 Mini Comp 1