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$. |
Scoring: Per Subtask
Authored by s17f18
Appeared in 2025 Mini Comp 1