题目描述

高桥在图书馆打工。图书馆有一个书架，上面有 $N$ 个储物格排成一行，从左到右编号为 $1, 2, \ldots, N$，每个储物格可以放一本书。初始时，所有储物格都是空的。

今天，高桥负责将 $M$ 本新到的书放到书架上。每本书应该放置的储物格编号是预先确定的：放置顺序为 $i$（$1 \le i \le M$）的书应该放在储物格 $S_i$。没有两本书放在同一个储物格，即 $S_1, S_2, \ldots, S_M$ 都是不同的值。高桥按照第 1 本、第 2 本、……、第 $M$ 本的顺序，一本一本地将书放到书架上。

为了提高效率，高桥想提前知道，在放置每本书时，"在当前为空的储物格中，这本书应该放的储物格是从左数第几个？"

具体来说，在放置第 $i$ 本书之前，如果我们将当前为空的储物格从左到右编号为 $1, 2, \ldots$，则储物格 $S_i$ 是从左数第 $P_i$ 个。对于每个 $i = 1, 2, \ldots, M$，求 $P_i$。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示储物格的总数和要放置的书的数量，用空格分隔。

第二行包含 $M$ 个整数 $S_1, S_2, \ldots, S_M$，表示每本书应该放置的储物格编号，用空格分隔。$S_i$ 表示放置顺序为 $i$ 的书的储物格编号。

输出格式

输出 $M$ 行。

第 $i$ 行输出一个整数 $P_i$，表示在放置第 $i$ 本书之前，从左到右数空储物格时，储物格 $S_i$ 的位置。

5 3
3 1 5

3
1
3

10 6
2 7 4 1 10 5

2
6
3
1
6
2

20 10
15 3 18 7 1 20 10 5 12 8

15
3
16
6
1
15
7
3
7
4

数据范围

• $1 \le M \le N \le 2 \times 10^5$
• $1 \le S_i \le N$
• 所有 $S_i$ 都不相同
• 所有输入值均为整数

知识点与难度

本题涉及的知识点从属于 GESP七级（树状数组、线段树），难度等级：中等。

来源

AtCoder AWC 0053E