C - Counting 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 人の生徒からなるクラスがあり、i\,(1 \leq i \leq N) 番目の生徒の身長は A_i です。

j=1,2,\ldots,Q について、以下の質問に答えてください。

  • N 人のうち、身長が x_j 以上の生徒は何人か？

制約

  • 1 \leq N,Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq x_j \leq 10^9
  • 入力は全て整数

入力

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

N Q
A_1 A_2 \ldots A_N
x_1
x_2
\vdots
x_Q

出力

Q 行出力せよ。

j\,(1 \leq j \leq Q) 行目には身長が x_j 以上の生徒の数を出力せよ。

入力例 1

3 1
100 160 130
120

出力例 1

2

身長が 120 以上の生徒は 2 番目の生徒と 3 番目の生徒です。

入力例 2

5 5
1 2 3 4 5
6
5
4
3
2

出力例 2

0
1
2
3
4

入力例 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

出力例 3

5
3
5
5
5

Score : 300 points

Problem Statement

There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.

For each j=1,2,\ldots,Q, answer the following question.

  • How many of the N students have a height of at least x_j?

Constraints

  • 1 \leq N,Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq x_j \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
x_1
x_2
\vdots
x_Q

Output

Print Q lines.

The j-th line (1 \leq j \leq Q) should contain the number of students with a height of at least x_j.

Sample Input 1

3 1
100 160 130
120

Sample Output 1

2

The students with a height of at least 120 are the 2-nd and 3-rd ones.

Sample Input 2

5 5
1 2 3 4 5
6
5
4
3
2

Sample Output 2

0
1
2
3
4

Sample Input 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

Sample Output 3

5
3
5
5
5