分数: 433 分
问题陈述
高桥正在图书馆做兼职。图书馆有一个书架,上面有 N 储物空间从左到右单排排列,每个储物空间可容纳一本书。存储空间已编号 1, 2, \ldots, N 从左到右。最初,所有存储空间都是空的。
今天,高桥负责放置 M 书架上新到的书。每本书应放置的存储空间编号是预先确定的:有放置顺序的书 i (1 \leq i \leq M) 被放置在存储空间中 S_i。没有两本书被放置在同一个存储空间中。也就是说, S_1, S_2, \ldots, S_M 都是不同的值。高桥按照第一本书、第二本书的顺序将书一本一本地放在书架上, \ldots, M第本书。
为了让任务更有效率,高桥想提前知道,在放置每本书时,“在当前空置的存储空间中,从左边算起这本书应该放在哪个位置?”
具体来说,在放置之前 i第本书,如果我们对当前空的存储空间进行编号 1, 2, \ldots 从左到右,存储空间 S_i 是 P_i从左起第一个。查找 P_i 对于每个 i = 1, 2, \ldots, M.
约束
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq S_i \leq N
- 全部 S_i 是不同的
- 所有输入值均为整数
输入
N M S_1 S_2 \ldots S_M
- 第一行包含一个整数 N 表示存储空间总数,一个整数 M 代表要放置的书籍数量,以空格分隔。
- 第二行包含存储空间编号 S_1, S_2, \ldots, S_M 每本书应放置的位置,并用空格分隔。
- S_i 表示有下单的图书的存储空间编号 i.
输出
P_1 P_2 \vdots P_M
- 输出 M 行。
- 关于 i第行,输出一个整数 P_i 代表存储空间的位置 S_i 在放置之前从左到右计算空闲存储空间时 i第本书。
示例输入 1
5 3 3 1 5
示例输出 1
3 1 3
示例输入 2
10 6 2 7 4 1 10 5
示例输出 2
2 6 3 1 6 2
示例输入 3
20 10 15 3 18 7 1 20 10 5 12 8
示例输出 3
15 3 16 6 1 15 7 3 7 4