← 返回题目列表

AtCoder · abc279_e

H. 作弊阿弥陀寺

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

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