← 返回题目列表

AtCoder · tessoku_book_cj

B11. 二分查找 2

中文机器翻译题面 查看原题

配点: 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