← 返回题目列表

AtCoder · awc0054_e

E. 图书馆书架指南

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

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