分数: 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