B - Quality Inspection and Product Disposal Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は工場の品質管理責任者です。工場では製造された製品の品質を定期的に検査し、基準を満たさない製品を廃棄する制度があります。

工場には現在 N 個の製品があり、各製品には 1 から N までの番号が付けられています。製品 i の品質スコアは A_i です。

高橋君は Q 回の品質検査を順番に行います。j 回目 (1 \leq j \leq Q) の検査では基準値 T_j が定められ、その時点でまだ廃棄されていない製品のうち、品質スコアが T_j 未満であるすべての製品を廃棄します。一度廃棄された製品は、以降の検査の対象にはなりません。なお、基準値 T_j は検査ごとにそれぞれ別々に定められるため、前回の基準値より小さくなることもあります。その場合、すでに前回以前の検査で該当する製品が廃棄済みであれば、新たに廃棄される製品はありません。

各検査の直後に、その検査で新たに廃棄された製品の個数を記録します。Q 回すべての品質検査について、各検査で新たに廃棄された製品の個数をそれぞれ求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq Q)
  • 入力はすべて整数である。

入力

N Q
A_1 A_2 \ldots A_N
T_1
T_2
\vdots
T_Q
  • 1 行目には、製品の個数を表す整数 N と、品質検査の回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各製品の品質スコアを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 続く Q 行のうち j 行目 (1 \leq j \leq Q) には、j 回目の検査の基準値を表す整数 T_j が与えられる。

出力

Q 行出力せよ。j 行目 (1 \leq j \leq Q) には、j 回目の検査で新たに廃棄された製品の個数を出力せよ。

入力例 1

5 3
3 1 4 1 5
2
4
3

出力例 1

2
1
0

入力例 2

8 5
10 5 3 8 7 2 6 1
4
3
7
7
9

出力例 2

3
0
2
0
2

入力例 3

15 6
15 3 9 7 12 1 20 5 11 2 8 18 4 6 14
5
10
8
15
15
1000000000

出力例 3

4
5
0
3
0
3

Score : 333 pts

Problem Statement

Takahashi is the quality control manager of a factory. The factory has a system where manufactured products are periodically inspected for quality, and products that do not meet the standards are disposed of.

The factory currently has N products, each numbered from 1 to N. The quality score of product i is A_i.

Takahashi performs Q quality inspections in order. In the j-th inspection (1 \leq j \leq Q), a threshold value T_j is set, and among the products that have not yet been disposed of at that point, all products whose quality score is strictly less than T_j are disposed of. Once a product is disposed of, it is no longer subject to subsequent inspections. Note that the threshold value T_j is determined independently for each inspection, so it may be smaller than the previous threshold. In that case, if the relevant products have already been disposed of in previous inspections, no new products are disposed of.

Immediately after each inspection, the number of products newly disposed of in that inspection is recorded. For all Q quality inspections, determine the number of products newly disposed of in each inspection.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq Q)
  • All input values are integers.

Input

N Q
A_1 A_2 \ldots A_N
T_1
T_2
\vdots
T_Q
  • The first line contains an integer N representing the number of products and an integer Q representing the number of quality inspections, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the quality scores of each product, separated by spaces.
  • In the following Q lines, the j-th line (1 \leq j \leq Q) contains an integer T_j representing the threshold value for the j-th inspection.

Output

Output Q lines. The j-th line (1 \leq j \leq Q) should contain the number of products newly disposed of in the j-th inspection.

Sample Input 1

5 3
3 1 4 1 5
2
4
3

Sample Output 1

2
1
0

Sample Input 2

8 5
10 5 3 8 7 2 6 1
4
3
7
7
9

Sample Output 2

3
0
2
0
2

Sample Input 3

15 6
15 3 9 7 12 1 20 5 11 2 8 18 4 6 14
5
10
8
15
15
1000000000

Sample Output 3

4
5
0
3
0
3