分数: 500 点
问题陈述
有一条幽灵腿,有 <var>N</var> 个垂直条和连接它们的 <var>M</var> 个水平条。 每个水平条都与垂直条垂直,并且它们的高度不同。 水平条<var>i</var> <var>(1 \leq i \leq M)</var> 连接垂直条<var>A_i</var> 和<var>A_i+1</var>。 让我们从竖条 <var>1</var> 的顶部开始追踪路径,并让 **score** 为我们到达底部的竖条的编号。 对于每个<var>i=1,2,\dots,M</var>,回答以下问题。 - 令<var>S_i</var> 为假设水平条<var>i</var> 被擦除的分数。找到<var>S_i</var>。 请注意,水平条实际上并未被删除,因此问题是相互独立的。 下面是对该问题的更正式的描述。给你一个长度序列 M 由之间的整数组成 1 和 N-1,包括: A=(A_1,A_2,\dots,A_M)。 回答以下问题 i=1, 2, \dots, M.
- 有一个序列 B=(B_1,B_2,\dots,B_N)。最初,我们有 B_j=j 对于每个 j。让我们执行以下操作 k=1, 2, \dots, i-1, i+1, \dots, M 按此顺序(换句话说,对于整数 k 之间 1 和 M 除了 i 按升序排列)。
- 交换以下值 B_{A_k} 和 B_{A_k+1}.
- 完成所有操作后,让 S_i 的值为 j 这样 B_j=1。查找 S_i.
约束
- 2 \leq N \leq 2\times 10^5
- 1 \leq M \leq 2\times 10^5
- 1 \leq A_i \leq N-1\ (1\leq i \leq M)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \dots A_M
输出
打印 M 行。 的 i第行 (1\leq i \leq M) 应包含值 S_i 作为整数。
示例输入 1
5 4 1 2 3 2
示例输出 1
1 3 2 4
对于 i = 2,操作发生变化 B 如下。
- 最初, B = (1,2,3,4,5).
- 执行以下操作 k=1。也就是说,交换以下值 B_1 和 B_2, 制作 B = (2,1,3,4,5).
- 执行以下操作 k=3。也就是说,交换以下值 B_3 和 B_4, 制作 B = (2,1,4,3,5).
- 执行以下操作 k=4。也就是说,交换以下值 B_2 和 B_3, 制作 B = (2,4,1,3,5).
经过所有操作,我们有 B_3=1,所以 S_2 = 3.
同样,我们有以下内容。
- 对于 i=1:执行以下操作 k=2,3,4 按此顺序使 B=(1,4,3,2,5),所以 S_1=1.
- 对于 i=3:执行以下操作 k=1,2,4 按此顺序使 B=(2,1,3,4,5),所以 S_3=2.
- 对于 i=4:执行以下操作 k=1,2,3 按此顺序使 B=(2,3,4,1,5),所以 S_4=4.
示例输入 2
3 3 2 2 2
示例输出 2
1 1 1
示例输入 3
10 10 1 1 1 9 4 4 2 1 3 3
示例输出 3
2 2 2 3 3 3 1 3 4 4