← 返回题目列表

AtCoder · past202005_j

J. 回转寿司

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

分数: 6 点

警告

2020 年 6 月 6 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

N 从未吃过寿司的孩子们来到了寿司回转场。 孩子们已被编号 1,2,3,\ldots,N.

传送带将传送 M 寿司盘子一一摆着。的美味 i第一个板是 a_i。 盘子会经过孩子面前 1, 2, 3, \ldots, N,按此顺序。

当一个盘子经过孩子面前时,当且仅当满足以下条件之一时,他/她才会拿起盘子并吃掉它:

  • 他/她从未拥有过盘子。
  • 这盘菜的美味程度比他/她迄今为止吃过的所有菜盘都要美味。

对于每个盘子,找到哪个孩子将拥有它。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 3 \times 10^5
  • 1 \leq a_i \leq 10^9

输入

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

N M
a_1 a_2 \cdots a_M

输出

打印 M 行。的 i- 第行应包含一个整数,表示将拥有 i第一个板,或 -1 如果没有孩子就会有盘子。


示例输入 1

2 5
5 3 2 4 8

示例输出 1

1
2
-1
2
1
  • 首先,传送带传送出一盘盘,盘中的美味 5.
    • 当车牌经过儿童面前时 1,他从未有过盘子,所以他得到了它。
  • 二、传送带传送一盘盘,盘中的美味 3.
    • 当车牌经过儿童面前时 1,味道并不比他吃过的那盘好吃,所以他就忽略了。
    • 当车牌经过儿童面前时 2,她从来没有吃过盘子,所以她得到了它。
  • 三、传送带传送一盘盘,里面的美味 2.
    • 当车牌经过儿童面前时 1,它的美味并不比他吃过的盘子好,所以他忽略了它。
    • 当车牌经过儿童面前时 2,味道并不比她吃过的盘子好,所以她就忽略了。
    • 当车牌经过儿童面前时 3,他从未有过车牌,所以他得到了这个车牌。
  • 四、传送带传送出一盘盘美味的食物 4.
    • 当车牌经过儿童面前时 1,它的美味并不比他吃过的盘子好,所以他忽略了它。
    • 当车牌经过儿童面前时 2,比她吃过的盘子好吃,所以她吃了。
  • 五、传送带传送一盘盘,盘中的美味 8.
    • 当车牌经过儿童面前时 1,比他吃过的盘子好吃,所以他就吃了。

示例输入 2

5 10
13 16 6 15 10 18 13 17 11 3

示例输出 2

1
1
2
2
3
1
3
2
4
5

示例输入 3

10 30
35 23 43 33 38 25 22 39 22 6 41 1 15 41 3 20 50 17 25 14 1 22 5 10 34 38 1 12 15 1

示例输出 3

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