B11 - Binary Search 2 解説 /

実行時間制限: 1 sec / メモリ制限: 1024 MB

配点: 1000

問題文

小さい順に並んでいるとは限らない、要素数 N の配列 A = [A_1, A_2, \cdots, A_N] が与えられます。それについて、以下の Q 個の質問に答えるプログラムを作成してください。

  • i (1 \leq i \leq Q) 個目の質問:配列 A には X_i より小さい要素が何個あるか?

制約

  • 1 \leq N, Q \leq 100000
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq X_i \leq 10^9 (1 \leq i \leq Q)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N
A_1 A_2 \cdots A_N
Q
X_1
X_2
\vdots
X_Q

出力

それぞれの質問に対する答えを、順番に Q 行出力してください。


入力例 1

15
83 31 11 17 32 19 23 37 43 47 53 61 67 5 55
5
10
20
30
40
50

出力例 1

1
4
5
8
10

入力例 2

5
1 3 3 3 1
2
4
3

出力例 2

5
2