← 返回题目列表

AtCoder · abc250_c

E. 相邻交换

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

分数: 300 点

问题陈述

N 球从左到右排成一排。 最初, i-th (1 \leq i \leq N) 左边的球有一个整数 i 。

高桥已表演 Q 操作。 的 i-th (1 \leq i \leq Q)操作如下。

  • 将球与整数交换 上面写着 x_i ,下一个球在右边。 如果球带有整数 上面写的 x_i 原本是最右边的球,与左边的下一个球交换。

让 a_i 是写在 i-th (1 \leq i \leq N) 操作后的球。 查找 a_1,\ldots,a_N.

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq x_i \leq N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N Q
x_1
\vdots
x_Q

输出

打印 a_1,\ldots,a_N,之间有空格。


示例输入 1

5 5
1
2
3
4
5

示例输出 1

1 2 3 5 4

操作执行如下。

  • 将球与 上面写着 1 ,下一个球在右边。 现在,球有整数 上面从左到右写着 2,1,3,4,5 。
  • 将球与 上面写着 2 ,下一个球在右边。 现在,球有整数 上面从左到右写着 1,2,3,4,5 。
  • 将球与 上面写着 3 ,下一个球在右边。 现在,球有整数 上面从左到右写着 1,2,4,3,5 。
  • 将球与 上面写着 4 ,下一个球在右边。 现在,球有整数 上面从左到右写着 1,2,3,4,5 。
  • 将球与 上面写着 5 ,下一个球在左边,因为它是最右边的球。 现在,球有整数 1,2,3,5,4 。

示例输入 2

7 7
7
7
7
7
7
7
7

示例输出 2

1 2 3 4 5 7 6

示例输入 3

10 6
1
5
2
9
6
6

示例输出 3

1 2 3 4 5 7 6 8 10 9