← 返回题目列表

AtCoder · abc382_c

E. 回转寿司

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

分数: 350 点

问题陈述

有 N 人数来自 1 to N 参观传送带寿司店。 的 美食级 人的 人的 i is A_i.

现在, M 寿司片将被放置在传送带上。 的 美味 的 j-th 寿司是 B_j。 每一块寿司从人们面前经过 1, 2, \dots, N 按此顺序。 每个人,当一份美味程度不低于自己美食水平的寿司从自己面前经过时,就会接过那份寿司来吃;否则,他们什么也不做。 那个人的寿司 i 拿东西和吃东西将不再从人面前经过 j\ (j > i).

对于每个 M 寿司,确定谁吃该寿司,或者是否没有人吃它。

约束

  • 1 \leq N, M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq 2 \times 10^5
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

输出

打印 M 行。 的 j- 第行 (1 \leq j \leq M)应包含代表吃该食物的人的数字 j-th 寿司,或 -1 如果没人吃的话。


示例输入 1

3 3
3 8 2
5 2 1

示例输出 1

1
3
-1
  • 第一个寿司:
    • 它首先从人面前经过 1。自从 B_1 \geq A_1, 人 1 拿起并吃掉它。
    • 不会从人面前经过 2 和 3.
  • 第二个寿司:
    • 它首先从人面前经过 1。自从 B_2 < A_1, 人 1 什么也不做。
    • 接下来,它从人面前经过 2。自从 B_2 < A_2, 人 2 什么也不做。
    • 终于经过人的面前了 3。自从 B_2 \geq A_3, 人 3 拿起并吃掉它。
  • 第三个寿司:
    • 它首先从人面前经过 1。自从 B_3 < A_1, 人 1 什么也不做。
    • 接下来,它从人面前经过 2。自从 B_3 < A_2, 人 2 什么也不做。
    • 终于经过人的面前了 3。自从 B_3 < A_3, 人 3 什么也不做。
    • 因此,没有人吃这个寿司。

示例输入 2

3 3
1 1 1
1 1 1

示例输出 2

1
1
1

示例输入 3

10 5
60 83 76 45 70 91 37 58 94 22
70 39 52 33 18

示例输出 3

1
7
4
10
-1