Problem 13072

You are given N integers a₁, a₂, ..., a_N, may contains same integers.

You need to answer Q queries: output how many integers of a₁, a₂, ..., a_N is less than or equal to x_i.

Note: Be careful of the efficiency of your strategy.

The first line contains one integer N (1 ≤ N ≤ 10⁵) – the number of integers you are given.

The second line contains N integers a₁, a₂, ..., a_N (-2 x 10⁹ ≤ a_i ≤ 2 x 10⁹).

The third line contains one integer Q (1 ≤ Q ≤ 10⁵) – the number of queries you need to answer.

Then Q lines follow. The i+3-th line contains one integer x_i (-2 x 10⁹ ≤ x_i ≤ 2 x 10⁹) – the i-th query.

It's guaranteed that:

For every i < N, x_i ≥ x_i+1(i.e every x_i must be less than or equal to the previous x_i).
For the first five testcases: 1 ≤ N ≤ 1000

For every query output how many integers of a₁, a₂, ..., a_N is less than or equal to x_i.

7
-2 5 2 5 7 9 10
5
11
10
8
1
-1

13072 - Gugulo