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